5
$\begingroup$

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?

$\endgroup$
4
  • $\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$ Mar 19, 2016 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, 2016 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, 2016 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, 2016 at 7:20

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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