Rozšířené formulace polytopů

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

Standardní projekty 19 (SGA0201500001)

Hlavní účastníci

Univerzita Karlova / Matematicko-fyzikální fakulta

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

15-11559S

Název projektu anglicky

Extended Formulation of Polytopes

Anotace anglicky

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.

Kategorie VaV

ZV - Základní výzkum

CEP - hlavní obor

IN - Informatika

CEP - vedlejší obor

—

CEP - další vedlejší obor

—

OECD FORD - odpovídající obory
(dle převodníku)

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Hodnocení poskytovatelem

U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)

Zhodnocení výsledků projektu

Projekt řeší problematiku rozšířené formulace polytopů, tedy objektů, které jsou projektovány na polytopy a mj. formulují optimalizační problém lineárním programováním. Výstupy přispívají k obecnému porozumění složitosti při odlišných formulacích těchto rozšíření, projekt řeší také použitelnost ve známých problémech typu TSP. Výstupy jsou publikační, nedostatky v dodržování pravidel se nevyskytly.

Zahájení řešení

1. 1. 2015

Ukončení řešení

31. 12. 2017

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

11. 4. 2017

Důvěrnost údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Systémové označení dodávky dat

CEP18-GA0-GA-U/02:1

Datum dodání záznamu

4. 5. 2018

Celkové uznané náklady

1 866 tis. Kč

Výše podpory ze státního rozpočtu

1 866 tis. Kč

Ostatní veřejné zdroje financování

0 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč