Polynomial size linear programs for problems in P

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Polynomial size linear programs for problems in P

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GA15-11559S" target="_blank" >GA15-11559S: Extended Formulation of Polytopes</a><br>

Continuities

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

Publication year

2019

Confidentiality

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

Name of the periodical

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Volume of the periodical

265

Issue of the periodical within the volume

červenec

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

18

Pages from-to

22-39

UT code for WoS article

000479018000003

EID of the result in the Scopus database

2-s2.0-85064318352