Timeline for Faster pseudo-polynomial time algorithms for PARTITION
Current License: CC BY-SA 2.5
33 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 11, 2018 at 22:23 | answer | added | hqztrue | timeline score: 3 | |
| Jul 8, 2015 at 19:57 | answer | added | Chao Xu | timeline score: 7 | |
| Feb 2, 2011 at 16:12 | comment | added | Yoshio Okamoto | @Saeed: I was thinking of the problem without equal-cardinality constraint. So, my "easy adaptation" doesn't work, and I was wrong. However, $O(n^2 A)$ is possible, by creating a 3-dimensional table $m[i,j,W]$ that represents the existence of a set in $\{1,...,i\}$ of cardinality $j$ with weight $W$. | |
| Feb 2, 2011 at 15:46 | comment | added | Saeed | @Yoshio Okamoto, this is not partition problem and I think it's strong NP problem and there is no pseudo polynomial algorithm with this, restriction of length of sets makes it difficault, I don't know how to reduce it, but it's not as simple as links you left. and @Firebrandt, how do you want solve it in O(n^2 A)? left it as answer, if it's true, I'll upvote it. | |
| Feb 2, 2011 at 12:42 | comment | added | Yoshio Okamoto | I'm a bit confused. There's an $O(nA)$-time algorithm for the knapsack problem and the partition problem (for example, see en.wikipedia.org/wiki/Knapsack_problem, and I've checked several textbooks, where this classical fact is presented). An easy adaptation should give an $O(nA)$-time algorithm for the proposed problem too. I don't see what I'm missing. | |
| Feb 2, 2011 at 11:36 | history | edited | Tsuyoshi Ito |
edited tags
|
|
| Feb 2, 2011 at 0:29 | comment | added | Suresh Venkat | since there's agreement, I just changed the title. | |
| Feb 2, 2011 at 0:28 | history | edited | Suresh Venkat | CC BY-SA 2.5 |
edited title
|
| Feb 1, 2011 at 23:38 | comment | added | Peter Shor | I agree ... the constraints on equal cardinality very likely will not change the complexity. | |
| Feb 1, 2011 at 21:23 | comment | added | Tsuyoshi Ito | I do not think that “with equal cardinality” is an essential part of the question. Therefore my suggestion is along “Faster pseudo-polynomial-time algorithm for the Partition problem.” | |
| Feb 1, 2011 at 21:13 | comment | added | Oleksandr Bondarenko | I suggest renaming question to "Partition problem with equal cardinality", since Partition and 2-Partition are different problems and the latter one is in P. | |
| Feb 1, 2011 at 20:56 | comment | added | Peter Shor | @Firebrandt: I took the liberty of editing your original question to add my version of your clarification (changing $O(nA)$ to $O(n^cA)$ with $c<2$, since I think even that's probably an open question). Feel free to change it back to $O(nA)$ if you want. I think the question, as clarified by your comments, is clearly research-level. | |
| Feb 1, 2011 at 20:54 | comment | added | Tsuyoshi Ito | @Peter: I confess that I did not read all the comments. | |
| Feb 1, 2011 at 20:54 | history | edited | Peter Shor | CC BY-SA 2.5 |
added clarification (from the OP in the comments) to the question.
|
| Feb 1, 2011 at 20:49 | comment | added | Peter Shor | @Tsuyoshi: it was clarified in the comments: "is there a pseudopolynomial time algorithm that runs in time $O(nA)$." (I agree it should have been clarified by editing the original post.) | |
| Feb 1, 2011 at 20:44 | comment | added | Tsuyoshi Ito | @Peter: I interpreted this question as asking whether the Partition problem with the additional restriction is solvable in polynomial time. That question can be an exercise in a course of computational complexity theory. | |
| Jan 31, 2011 at 19:27 | comment | added | Peter Shor | How is this too elementary? The obvious approach gives $O(n^2A)$, and the question is whether there's a better algorithm running in time $O(n^c A)$ where $c < 2$. My guess is that this is an open question. | |
| Jan 31, 2011 at 4:01 | comment | added | Kaveh | Firebrandt, could you please explain why you are searching for a solution to "the 2-Partition problem"? e.g. are you working on some other research problem which is related to this question? Note that this site is for research level questions, so if the question is not research level and there is not a good research related motivation for it then it is probably not appropriate for cstheory and may get closed as off-topic. (you may want to try Math.SE.) | |
| Jan 30, 2011 at 21:22 | comment | added | Tsuyoshi Ito | @Oleksandr: I do not have an answer, in general or for this specific question. I am thinking about voting to close this question. | |
| Jan 30, 2011 at 21:17 | comment | added | Oleksandr Bondarenko | @Tsuyoshi: Should it be closed if it's "on the border of being too elementary"? | |
| Jan 30, 2011 at 20:55 | comment | added | Tsuyoshi Ito | I am afraid that this question is on the border of being too elementary. For example, “Is the Partition problem with the additional restriction that the two sets must have equal cardinality still NP-complete?” can be a typical homework question and I am afraid that writing down the answer may have negative impact on some courses in computational complexity. | |
| Jan 30, 2011 at 17:01 | comment | added | Firebrandt | I am searching for solutions to the optimisation version of the 2-Partition problem en.wikipedia.org/wiki/Partition_problem (as given in wiki) - "Find a partition into two subsets S1,S2 such that \max(\operatorname{sum}(S_1), \operatorname{sum}(S_2)) is minimized (sometimes with the additional constraint that the sizes of the two sets in the partition must be equal, or differ by at most 1 )". This problem differs from the standard partition problem in that, the cardinality of the subsets must be equal(even) , or differ by 1(odd) | |
| Jan 30, 2011 at 16:47 | comment | added | Kaveh | Firebrandt, could you please explain the motivation behind this question, i.e. why are you interested in this question? | |
| Jan 30, 2011 at 16:47 | comment | added | Oleksandr Bondarenko | @Firebrandt: Could you, please, add the clarification what you meant by better in your question. What do you mean by outlining the solution - how to fill table entries in the table from Garey and Johnson book? | |
| Jan 30, 2011 at 16:41 | comment | added | Firebrandt | If so , could you please outline the solution? thanks! | |
| Jan 30, 2011 at 16:38 | comment | added | Firebrandt | @Oleksandr , by better I meant is there a pseudo polynomial algorithm which runs in O(nA). sorry that i am unable to post in latex. | |
| Jan 30, 2011 at 16:14 | comment | added | Oleksandr Bondarenko | @Firebrandt: Book says that it can be solved "in time bounded by low order polynomial in the number of table entries", and this doesn't imply $\mathcal{O}(nA)$. Thus it's possible that you can't do better. | |
| Jan 30, 2011 at 16:07 | comment | added | Oleksandr Bondarenko | @Firebrandt: Please, specify your question: what do you mean by "better"? | |
| Jan 30, 2011 at 16:06 | comment | added | Firebrandt | @Oleksandr, THanks for that. Could you also please tell me how to solve it in O(nA) , the book just says it can be solved so. | |
| Jan 30, 2011 at 15:46 | history | edited | Hsien-Chih Chang 張顯之 | CC BY-SA 2.5 |
added 34 characters in body; edited tags
|
| Jan 30, 2011 at 14:15 | history | tweeted | twitter.com/#!/StackCSTheory/status/31717240323710977 | ||
| Jan 30, 2011 at 14:10 | comment | added | Mathieu Chapelle | Notice that as a special case of Knapsack, it has an FPTAS. See e.g. E.L.Lawler. Fast approximation algorithms for knapsack problems. | |
| Jan 30, 2011 at 13:13 | history | asked | Firebrandt | CC BY-SA 2.5 |