In formulating optimization problems as LPs, adding extra variables can greatly reduce the size of the LP. An extension of a polytope is such a formulation that projects onto the original LP formulation of the problem. In this model, LP formulations of some problems in P that have exponential size can be reduced to polynomial size in higher dimensions. Extension complexity is concerned with finding bounds on the sizes of extensions for specific computational problems.This workshop will review the start of the art on the subject and provide ideas for future directions of research.

Date and Venue

Date: June 9 (Mon), 15:00 -- 18:00
Place: Kyoto University Centennial Memorial Hall (A workshop in Computational Geometry Week 2014)


Abstracts of Talks


Free of charge for the registered participants of SoCG 2014.
Others may register from the SoCG webpage (1-day workshop registration).