Polynomial size linear programs for problems in P

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10398319" target="_blank" >RIV/00216208:11320/19:10398319 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=d33QHykc.L" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=d33QHykc.L</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2019.03.016" target="_blank" >10.1016/j.dam.2019.03.016</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Polynomial size linear programs for problems in P

Popis výsledku v původním jazyce

A perfect matching in an undirected graph G = (V, E) is a set of vertex disjoint edges from E that include all vertices in V. The perfect matching problem is to decide if G has such a matching. Recently Rothvoss proved the striking result that the Edmonds&apos; matching polytope has exponential extension complexity. In this paper for each n = vertical bar V vertical bar we describe a polytope for the perfect matching problem that is different from Edmonds&apos; polytope and define a weaker notion of extended formulation. We show that the new polytope has a weak extended formulation (WEF) Q of polynomial size. For each graph G with n vertices we can readily construct an objective function so that solving the resulting linear program over Q decides whether or not G has a perfect matching. With this construction, a straightforward O(n(4)) implementation of Edmonds&apos; matching algorithm using O(n(2)) bits of space would yield a WEF Q with O(n(6) log n) inequalities and variables. The construction is uniform in the sense that, for each n, a single polytope is defined for the class of all graphs with n nodes. The method extends to solve polynomial time optimization problems, such as the weighted matching problem. In this case a logarithmic (in the weight of the optimum solution) number of optimizations are made over the constructed WEF. The method described in the paper involves the construction of a compiler that converts an algorithm given in a prescribed pseudocode into a polytope. It can therefore be used to construct a polytope for any decision problem in P which can be solved by a well defined algorithm. Compared with earlier results of Dobkin-Lipton-Reiss and Valiant our method allows the construction of explicit linear programs directly from algorithms written for a standard register model, without intermediate transformations. We apply our results to obtain polynomial upper bounds on the non-negative rank of certain slack matrices related to membership testing of languages in P/POLY. (C) 2019 Elsevier B.V. All rights reserved.

Název v anglickém jazyce

Polynomial size linear programs for problems in P

Popis výsledku anglicky

A perfect matching in an undirected graph G = (V, E) is a set of vertex disjoint edges from E that include all vertices in V. The perfect matching problem is to decide if G has such a matching. Recently Rothvoss proved the striking result that the Edmonds&apos; matching polytope has exponential extension complexity. In this paper for each n = vertical bar V vertical bar we describe a polytope for the perfect matching problem that is different from Edmonds&apos; polytope and define a weaker notion of extended formulation. We show that the new polytope has a weak extended formulation (WEF) Q of polynomial size. For each graph G with n vertices we can readily construct an objective function so that solving the resulting linear program over Q decides whether or not G has a perfect matching. With this construction, a straightforward O(n(4)) implementation of Edmonds&apos; matching algorithm using O(n(2)) bits of space would yield a WEF Q with O(n(6) log n) inequalities and variables. The construction is uniform in the sense that, for each n, a single polytope is defined for the class of all graphs with n nodes. The method extends to solve polynomial time optimization problems, such as the weighted matching problem. In this case a logarithmic (in the weight of the optimum solution) number of optimizations are made over the constructed WEF. The method described in the paper involves the construction of a compiler that converts an algorithm given in a prescribed pseudocode into a polytope. It can therefore be used to construct a polytope for any decision problem in P which can be solved by a well defined algorithm. Compared with earlier results of Dobkin-Lipton-Reiss and Valiant our method allows the construction of explicit linear programs directly from algorithms written for a standard register model, without intermediate transformations. We apply our results to obtain polynomial upper bounds on the non-negative rank of certain slack matrices related to membership testing of languages in P/POLY. (C) 2019 Elsevier B.V. All rights reserved.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GA15-11559S" target="_blank" >GA15-11559S: Rozšířené formulace polytopů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

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

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

265

Číslo periodika v rámci svazku

červenec

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

22-39

Kód UT WoS článku

000479018000003

EID výsledku v databázi Scopus

2-s2.0-85064318352