Skip to main content
10 events
when toggle format what by license comment
Jan 5, 2014 at 20:44 vote accept CommunityBot
Dec 26, 2013 at 8:48 history edited Marzio De Biasi CC BY-SA 3.0
Sasho's comment fix
Dec 26, 2013 at 8:36 comment added Marzio De Biasi @SashoNikolov: yes, I mean that for every pair $(x_{2i-1},x_{2i})$ (and in the proof $(x'_{2i-1}, x'_{2i})$) exactly one is included in $X_1$; I'll edit the answer
Dec 26, 2013 at 7:46 comment added Sasho Nikolov also I believe you mis-state the even-odd partition problem. if no two consecutive vectors can be in the same set the problem is trivial. i believe you mean that $|X_i \cap \{x_{2j-1}, x_{2j}\}| = 1$ is required for all $i \in \{1, 2\}$ and $1 \leq j \leq m$
Dec 26, 2013 at 0:41 comment added Sasho Nikolov what you call 0-1 vector partition is equivalent to the problem of determining if a set system has discrepancy 0. this is NP hard, since it captures e.g. the 2-2-set-splitting problem, see thm 9 in this paper by guruswami cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps; my paper has a bit more on the hardness of discrepancy paul.rutgers.edu/~anikolov/Files/charikarM.pdf
Dec 25, 2013 at 21:30 history edited Marzio De Biasi CC BY-SA 3.0
0-1 vector equal subset sum details
Dec 25, 2013 at 21:25 history edited Marzio De Biasi CC BY-SA 3.0
0-1 vector equal subset sum details
Dec 25, 2013 at 20:36 history edited Marzio De Biasi CC BY-SA 3.0
exponent fixed in the even odd reduction
Dec 25, 2013 at 19:51 history edited Marzio De Biasi CC BY-SA 3.0
added 118 characters in body
Dec 25, 2013 at 19:45 history answered Marzio De Biasi CC BY-SA 3.0