Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Say we have a polyhedron in standard form:

\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\ \mathbf{x} \ge 0 \end{array} \end{equation*}

Are there any known methods for finding a hyperplane $\mathbf{d} \mathbf{x} +d_0= 0$ that splits the polyhedron in a way that the number of vertices on each side of the hyperplane is approximately the same? (i.e. an algorithm that minimizes the absolute difference of vertex cardinalities on the two sides of the split).

Also, are there any known results regarding the complexity of this problem?

Addendum: Restricting the types of cuts:

Here is a variation of the original problem with the hope that it is easier to solve than the original one:

Is there a way to efficiently compute or estimate for which coordinate $i$ a hyperplane of the form $d_ix_i + d_0 = 0$ would yield the lowest absolute difference of vertex cardinalities on both sides of the split? By efficient I mean anything more efficient than the exhaustive enumeration of vertex cardinalities for all possible such splits.

Note: After a few days of little progress, I posted this question at MathOverflow too.

share|improve this question
    
Shouldn't one be able to prove this is an NP-hard problem? –  Peter Shor Sep 8 '11 at 18:38
    
Thanks @Peter. A proof would be great. That said, I presume the problem is hard, and I think I am more interested in heuristics or approximation algorithms. The motivation behind the idea of restricting the types of cuts was in part to see if there are easier variations of the general problem for which we already know a solution or an approximation algorithm. –  user815423426 Sep 8 '11 at 18:47
    
How about something along these lines (not sure if it works) - We know counting the number of maximum bipartite matchings is #P-hard. We also know that a linear program to find a maximum bipartite matching is totally unimodular and thus any corner point/basic feasible solution is integral. For a maximum bipartite matching problem, find the value of the matching. Construct a linear program with the constraint that any solution has to have the optimal value. Then every corner point is a matching. Being able to repeatedly divide evenly means you should be able to count the number of matchings. –  Sid Sep 8 '11 at 19:21
    
Never mind. One would also have to be able to count the number of vertices added by the cutting plane. –  Sid Sep 8 '11 at 19:55
add comment

1 Answer

I can't remember the analytic way to do this!

But this a classical problem for Genetic Programming! If you are familiar with it you can use a normalized vectors in the center of the polyhedron that describes the cutting plane.

So your population is a set of [x,y,z,...] normalized vectors and as fitting function you use the difference between the 2 split volumes!

So, if the difference tends to zero more "fit" is your vector/plane!

share|improve this answer
    
Sorry, could you say that again without using genetic-programming language? What's a "population"? What's a "fitting function"? –  JɛffE Sep 9 '11 at 7:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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