4
$\begingroup$

Can anyone suggest a text on polyhedral theory? Particularly on increasing the number of faces under projections. 0,1 polytopes

$\endgroup$
1
  • 4
    $\begingroup$ Günter M. Ziegler's Lectures on Polytopes (Springer link) is superb, but may not be the best source for your specific interests (upon which you might elaborate). $\endgroup$ – Joseph O'Rourke Aug 6 '14 at 20:28
5
$\begingroup$

Reading between the lines of your comment about increasing the number of faces under projections, I'm guessing that you're interested in the subject known as "extension complexity." Starting with some complicated polytope like the traveling salesman polytope, one wants to know if it is the projection of a much simpler polytope in slightly higher dimension. This recent paper by Fiorini et al. has a lot of relevant references. This is an active research area so I think there is no single book that really covers the area properly.

But if you're instead looking for a general textbook treatment of polyhedral theory in the context of combinatorial optimization, a standard reference is Schrijver's magnum opus Combinatorial Optimization: Polyhedra and Efficiency.

$\endgroup$
4
$\begingroup$

General references on polytopes are:

A interesting survey about 0/1 polytopes was written by Ziegler in 2000 and appeared in "Polytopes -- Combinatorics and Computation" published by Birkhäuser (in the DMV Seminar series).

A paper that might be of interest to you is Rothvoß: Some 0/1 polytopes need exponential size extended formulations.

$\endgroup$
0
2
$\begingroup$

For me, the classical reference on polyhedral theory is Schrijver's 'Theory of Linear and Integer Programming', together with the Combinatorial Optimization monograph that was mentioned above.

If you have a more specific concern, please specify your question.

$\endgroup$

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.