Timeline for Generating all possible subsets in order of sum
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 17 at 22:55 | comment | added | LSpice | How does \eqref{467374_P} become empty? You only add to it, never remove anything from it. I guess you mean the solution set is empty? In that case, although it probably doesn't much matter, since you know how many sets you're emitting, you can just keep track and stop when you've emitted them all. | |
| Aug 17 at 22:54 | history | edited | LSpice | CC BY-SA 4.0 |
`\label`+`\eqref` while this is on the front page
|
| S Mar 20 at 20:10 | review | First answers | |||
| Mar 21 at 4:17 | |||||
| S Mar 20 at 20:10 | history | suggested | Matemáticos Chibchas | CC BY-SA 4.0 |
Minor improvement in LaTeX formatting
|
| Mar 20 at 16:51 | review | Suggested edits | |||
| S Mar 20 at 20:10 | |||||
| S Mar 20 at 14:03 | review | First answers | |||
| Mar 20 at 15:46 | |||||
| S Mar 20 at 14:03 | history | edited | BADJARA Mohamed el Amine | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Mar 20 at 12:15 | comment | added | BADJARA Mohamed el Amine | We must choose a subset among others, it is a combinatoric problem which is NP-complete, the proposed method in the general case at the first step is $O(\sqrt n)$, by adding the constraint at step 4, it will be $O(2^n)$ in the general case, but practically, it will be really speed up because we begin from the optimal solution. The inconvenient here is the program must use the Branch and Bound procedure to resolve it. | |
| Mar 20 at 11:57 | comment | added | Peter Taylor | It's certainly not going to be amortised $O(1)$ per subset. | |
| Mar 20 at 11:44 | comment | added | Alex M. | Can you prove that this runs in polynomial time, as required by the OP? | |
| Mar 20 at 11:28 | history | edited | BADJARA Mohamed el Amine | CC BY-SA 4.0 |
deleted 1 character in body
|
| S Mar 20 at 11:10 | review | First answers | |||
| Mar 20 at 11:44 | |||||
| S Mar 20 at 11:10 | history | answered | BADJARA Mohamed el Amine | CC BY-SA 4.0 |