A polytope Q is called an extended formulation or extension of another polytope P if P is a projection of Q. In many
cases, the description of Q is much smaller than that of P and this allows one to speed up linear optimization over
P by optimizing over Q. In some cases, the size of the extension can be exponentially smaller than that of P and
can mean a difference between polynomial and superpolynomial/exponential.
Extended formulations arise frequently in combinatorial optimization, and their study has seen a renewed interest
over recent years. More importantly, important connections betwe
Last update: JUDr. Dana Macharová (13.01.2014)
Polytop Q je rozšířenou formulací jiného polytopu P když P je projekcí Q. V mnoha případech je popis Q mnohem
menší než popis P, a toto umožňuje rychlejší optimalizaci na Q než na P. Zrychlení může být až z exponenciální
metody na polynomiální.
Rozšířené formulace se často objevují v kombinatorické optimalizaci, a jsou známy zajímavé souvislosti s
maticovými faktorizacemi či komunikační složitostí, které budou také součástí přednášky.
Literature -
Last update: JUDr. Dana Macharová (13.01.2014)
[1] D. Avis and H.R. Tiwary. On the extension complexity of combinatorial polytopes. CoRR, abs/1302.2340, 2013.
[2] Y. Faenza, S. Fiorini, R. Grappe, and H.R. Tiwary. Extended formulations, non-negative factorizations and randomized communication protocols. CoRR, abs/1105.4127, 2011.
[3] S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf. Linear vs. semi-definite extended formulations: Exponential separation and strong lower bounds. CoRR, abs/1111.0837, 2011.
[4] M. R. Garey and D. S. Johnson. Computers and intractability; a guide to the theory of NP-completeness. W.H. Freeman, 1979.
[5] E. Kushilevitz and N. Nisan. Communication complexity. Cambridge University Press, Cambridge, 1997.
[6] M. Yannakakis. Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3):441?466, 1991.
[7] G.M. Ziegler. Lectures on polytopes, volume 152 of Graduate Texts in Mathematics. Springer, 1995.
Last update: JUDr. Dana Macharová (13.01.2014)
[1] D. Avis and H.R. Tiwary. On the extension complexity of combinatorial polytopes. CoRR, abs/1302.2340, 2013.
[2] Y. Faenza, S. Fiorini, R. Grappe, and H.R. Tiwary. Extended formulations, non-negative factorizations and randomized communication protocols. CoRR, abs/1105.4127, 2011.
[3] S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf. Linear vs. semi-definite extended formulations: Exponential separation and strong lower bounds. CoRR, abs/1111.0837, 2011.
[4] M. R. Garey and D. S. Johnson. Computers and intractability; a guide to the theory of NP-completeness. W.H. Freeman, 1979.
[5] E. Kushilevitz and N. Nisan. Communication complexity. Cambridge University Press, Cambridge, 1997.
[6] M. Yannakakis. Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3):441?466, 1991.
[7] G.M. Ziegler. Lectures on polytopes, volume 152 of Graduate Texts in Mathematics. Springer, 1995.
