Extended Formulation of Polytopes
Project goals
In this project we focus on applying the theory of extended formulations to studying the computational complexity of combinatorial problems. We will formalize how to canonically represent optimization problems as optimization over a suitable polytope. This representation must be natural and should also capture equivalence between problems by a suitable equivalence between the associated polytopes. To this end, we will study the subset of polynomial reductions that allow one to translate lower bounds for extended formulation of the associated polytopes. Since extended formulations do not capture polynomial time complexity class exactly, we will also study refinements to the model that on the one hand capture the classical complexity classes nicely, and on the other hand allow us to prove meaningful lower bounds for hard problems. During the course of the project, we will devise new tools that can be applied to computational problems as well, such as how efficiently can one construct a good linear programming formulation for a problem given a formulation for a related problem.
Keywords
Extended FormulationsPolytopesLinear ProgrammingCombinatorial OptimizationComputational ComplexityTheory of AlgorithmsLower BoundsP vs. NP
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 19 (SGA0201500001)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
15-11559S
Alternative language
Project name in Czech
Rozšířené formulace polytopů
Annotation in Czech
Projekt se zaměří na aplikaci teorie rozšířených formulací polytopů v studiu výpočetní složitosti kombinatorických problémů. Chceme formalizovat způsob kanonické reprezentace problémů kombinatorické optimalizace jako optimalizace na vhodném polytopu. Způsob, jakým je polytop asociován s problémem, musí být přirozený a musí také zachycovat ekvivalenci mezi problémy pomocí vhodné ekvivalence mezi asociovanými polytopy. Za tímto účelem budeme studovat některé polynomiální převody, které umožňují převést dolní odhady pro rozšířenou formulaci asociovaných polytopů. Jelikož rozšířené formulace nezachycují třídu problémů řešitelných v polynomiálním čase přesně, budeme taky studovat zjemnění modelu, které jednak správně zachycuje klasické třídy výpočetní složitosti, ale rovněž nám umožňuje dokázat smysluplné dolní odhady pro těžké problémy. Nástroje, které vynalezneme během projektu, lze také aplikovat na výpočetní problémy, kupříkladu jak efektivně můžeme zkonstruovat dobrou formulaci lineárního programování pro nějaký problém, když už známe formulaci nějakého příbuzného problému.
Scientific branches
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project deals with extended formulations of polytopes, i.e., the objects that project to polytopes and could be seen as linear programming formulations of the optimization problem over these polytopes. The outputs contribute to the general knowledge of the complexity implied by different ways of extensions, they also resolve extension complexity for related optimization problems such as TSP.
Solution timeline
Realization period - beginning
Jan 1, 2015
Realization period - end
Dec 31, 2017
Project status
U - Finished project
Latest support payment
Apr 11, 2017
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP18-GA0-GA-U/02:1
Data delivery date
May 4, 2018
Finance
Total approved costs
1,866 thou. CZK
Public financial support
1,866 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
1 866 CZK thou.
Public support
1 866 CZK thou.
100%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2015 - 31. 12. 2017