I have the following problem in mind. Suppose we have an $n$-dimensional point cloud with $m$ points. Each point in the cloud is associated with a value $X_i,1\leq i\leq m$. I would like to use a hyperplane to partition this point cloud into two parts, $S$ and $S^c$, in order to maximize $\sum_{i\in S} X_i$. Are there any efficient ways to do it?

Any advice would be greatly appreciated. If this cannot be solved efficiently, do there exist a good approximation algorithm?

  • $\begingroup$ Presumably there aren't any bounds on the values of $X_i$? For example, a heavy positive point must be in $S$ and a heavy negative point must be in $S^c$? $\endgroup$ – Jared Goguen Mar 19 '16 at 8:53
  • $\begingroup$ 1. Are the values all non-negative? Or can they be negative? 2. Is $m$ potentially larger than $n$? 3. What approaches have you considered? You might want to look into soft-margin SVM and how it finds a linear separating hyperplane. $\endgroup$ – D.W. Mar 19 '16 at 21:17
  • $\begingroup$ @JaredGoguen There could be good bounds on $X_i$, for example, we know that it lies between [-3,3]. But there is no additional information.. $\endgroup$ – Jiantao Mar 20 '16 at 7:18
  • $\begingroup$ @D.W. Some values are positive and some values are negative. In general, $m$ is much bigger than $n$, and $n$ is usually not very big (as most 200). I indeed have tried to look at soft-margin SVM, but it gives me no clue on how good that solution might be compared to the optimal solution of the original problem... $\endgroup$ – Jiantao Mar 20 '16 at 7:20

The special case of your problem in which the points are in $\{-1,1\}^n$ and the values are $\pm 1$ is known as Maximum Agreement for Halfspaces. When talking about approximation, we want a positive objective function, and in this case it is convenient to ask for the number of correctly classified points. A point is correctly classified if either its value is $+1$ and it belongs to $S$, or its value is $-1$ and it belongs to $S^c$.

A trivial $1/2$-approximation algorithm just picks any halfspace and chooses either the halfspace or its complement. One of these satisfies at least half the constraints. Guruswami and Raghavendra showed that no better polynomial time approximation algorithm exists unless $\mathsf{P}=\mathsf{NP}$.

In practice you might be able to use some heuristics, but these of course don't provide any guarantees in the worst case.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.