2011

Combinatorial Bounds on Nonnegative Rank and Extended Formulations

Fiorini, Samuel, Kaibel, Volker, Pashkovich, Kanstantsin et al.

Understand

An extended formulation of a polytope P is a polytope Q which can be projected onto P.

Extended formulations of small size (i.e., number of facets) are of interest, as they allow to model corresponding optimization problems as linear programs of small sizes.
The main known lower bounds on the minimum sizes of extended formulations for fixed polytope P (Yannakakis 1991) are closely related to the concept of nondeterministic communication complexity.
We study the relative power and limitations of the bounds on several examples.

Built on

On an extremal problem in graph theory
P. Turán · 1941
Earlier work this paper cites.
Maximum matching and a polyhedron with 0, 1 vertices
J. Edmonds · 1965
Earlier work this paper cites.
On certain polytopes associated with graphs
V. Chvátal · 1975
Earlier work this paper cites.
On the ratio of optimal integral and fractional covers
L. Lovász · 1975
Earlier work this paper cites.
Factorization of nonnegative matrices. II
Cony M. Lau and Thomas L. Markham · 1978
Earlier work this paper cites.
Some complexity questions related to distributed computing
A. C. Yao · 1979
Earlier work this paper cites.
The Boolean rank of zero-one matrices
D. de Caen, D. A. Gregory, and N. J. Pullman · 1981
Earlier work this paper cites.
Semiring rank: Boolean rank and nonnegative rank factorizations
D. A. Gregory and N. J. Pullman · 1983
Earlier work this paper cites.
Covering of graphs by complete bipartite subgraphs: complexity of 0 0 - 1 1 matrices
Z. Tuza · 1984
Earlier work this paper cites.
Disjunctive programming and a hierarchy of relaxations for discrete optimization problems
E. Balas · 1985
Earlier work this paper cites.
Using separation algorithms to generate mixed integer model reformulations
R. K. Martin · 1991
Earlier work this paper cites.
Expressing combinatorial optimization problems by linear programs
M. Yannakakis · 1991
Earlier work this paper cites.
A comparison of two lower-bound methods for communication complexity
M. Dietzfelbinger, J. Hromkovič, and G. Schnitger · 1994
Earlier work this paper cites.

Similar

Fractional covers and communication complexity
M. Karchmer, E. Kushilevitz, and N. Nisan · 1995
Cited alongside, same era.
Lectures on Polytopes
G. M. Ziegler · 1995
Cited alongside, same era.
Communication complexity
E. Kushilevitz and N. Nisan · 1997
Cited alongside, same era.
Biclique covers and partitions of bipartite graphs and digraphs and related matrix ranks of { 0 , 1 } \{0,1\} -matrices
Faun C. C. Doherty, J. Richard Lundgren, and Daluss J. Siewert · 1999
Cited alongside, same era.
On polyhedral approximations of the second-order cone
A. Ben-Tal and A. Nemirovski · 2001
Cited alongside, same era.
Combinatorial optimization. Polyhedra and efficiency. Vol. B
A. Schrijver · 2003
Cited alongside, same era.
Computational aspects of the 2-dimension of partially ordered sets
M. Habib, L. Nourine, O. Raynaud, and E. Thierry · 2004
Cited alongside, same era.
Real rank versus nonnegative rank
LeRoy B. Beasley and Thomas J. Laffey · 2009
Cited alongside, same era.
Smallest compact formulation for the permutahedron
M. X. Goemans · 2009
Cited alongside, same era.
Symmetry in extended formulations of the permutahedron
Original
K. Pashkovich · 2009
Cited alongside, same era.
On the complexity of nonnegative matrix factorization
S. A. Vavasis · 2009
Cited alongside, same era.
Extended formulations in combinatorial optimization
M. Conforti, G. Cornuéjols, and G. Zambelli · 2010
Cited alongside, same era.

Then

On the geometric interpretation of the nonnegative rank
Original
N. Gillis and F. Glineur · 2010
Later among the works it cites.
A counterexample to the Alon-Saks-Seymour conjecture and related problems
Original
H. Huang and B. Sudakov · 2010
Later among the works it cites.
Symmetry matters for the sizes of extended formulations
V. Kaibel, K. Pashkovich, and D.O. Theis · 2010
Later among the works it cites.
Reformulation and decomposition of integer programs
F. Vanderbeck and L. A. Wolsey · 2010
Later among the works it cites.
Extended formulations, non-negative factorizations and randomized communication protocols
Original
Y. Faenza, S. Fiorini, R. Grappe, and H.R. Tiwary · 2011
Closest in time.
Extended formulations for polygons
Original
S. Fiorini, T. Rothvoß, and H.R. Tiwary · 2011
Closest in time.
Lifts of convex sets and cone factorizations
Original
João Gouveia, Pablo A. Parrilo, and Rekha Thomas · 2011
Closest in time.
Extended formulations in combinatorial optimization
V. Kaibel · 2011
Closest in time.
Finding descriptions of polytopes via extended formulations and liftings
Original
V. Kaibel and A. Loos · 2011
Closest in time.
Constructing extended formulations from reflection relations
V. Kaibel and K. Pashkovich · 2011
Closest in time.
Some 0/1 polytopes need exponential size extended formulations
Original
T. Rothvoß · 2011
Closest in time.
Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds
S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf · 2012
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…