Timeline for Prove the NP-hardness of the following problem: Whether there exists a partition for a set of data points
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 20 at 20:12 | comment | added | Robeto Leo | Thanks, that helps! I ll think about if we restrict $x_j$ to be binary! | |
| Mar 19 at 19:20 | comment | added | David Feldman | Thought: Your question implicitly defines a polyhedral complex, call it, say, the disjoint-reasons hull, so all the points in the convex hull for disjoint reasons. It's the union of a lot of intersections of simplexes. A related but purely geometrical question would ask how complicated this complex get (number of vertices, edges, etc.) | |
| Mar 19 at 19:11 | comment | added | David Feldman | Thought: Is the problem any easier if $x_1,\ldots,x_m\in \{0.1\}^n$? That has a more combinatorial flavor. Maybe that's already NP-hard, and maybe still if you assume $x_0=(1/2,1/2,\ldots)$. | |
| Mar 18 at 12:30 | comment | added | Robeto Leo | I should be clearer. $x_0, x_1, ..., x_m \in \mathbb{Q}^n$, and $[m] = \{1,...,m\}$. $conv(\cdot)$ means the convex hull of the input. Both $n, m$ are not fixed. | |
| Mar 18 at 6:01 | comment | added | Lajos Soukup | For fixed n it is polynomial in m. en.m.wikipedia.org/wiki/… | |
| Mar 18 at 5:40 | comment | added | David Feldman | I'm having trouble with your notation. 1) If this is a computational decision problem, what do you mean by input size if the vectors are real-valued? 2) What do you mean by $[m]$? If [m] means $\{1,\ldots,m\}$ I suggest using another notation for $x_0$ seeing as it has a completely different role in the story. 3) I'm guessing that conv mean convex hull? | |
| S Mar 18 at 5:25 | review | First questions | |||
| Mar 18 at 13:24 | |||||
| S Mar 18 at 5:25 | history | asked | Robeto Leo | CC BY-SA 4.0 |