Extended Formulation of Polytopes
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
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
—
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
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