English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The groundbreaking work of Rothvo{\ss} [arxiv:1311.2369] established thatevery linear program expressing the matching polytope has an exponential numberof inequalities (formally, the matching polytope has exponential extensioncomplexity). We generalize this result by deriving strong bounds on thepolyhedral inapproximability of the matching polytope: for fixed $0 <\varepsilon < 1$, every polyhedral $(1 + \varepsilon / n)$-approximationrequires an exponential number of inequalities, where $n$ is the number ofvertices. This is sharp given the well-known $\rho$-approximation of size$O(\binom{n}{\rho/(\rho-1)})$ provided by the odd-sets of size up to$\rho/(\rho-1)$. Thus matching is the first problem in $P$, whose naturallinear encoding does not admit a fully polynomial-size relaxation scheme (thepolyhedral equivalent of an FPTAS), which provides a sharp separation from thepolynomial-size relaxation scheme obtained e.g., via constant-sized odd-setsmentioned above.  Our approach reuses ideas from Rothvo{\ss} [arxiv:1311.2369], however themain lower bounding technique is different. While the original proof is basedon the hyperplane separation bound (also called the rectangle corruptionbound), we employ the information-theoretic notion of common information asintroduced in Braun and Pokutta [http://eccc.hpi-web.de/report/2013/056/],which allows to analyze perturbations of slack matrices. It turns out that thehigh extension complexity for the matching polytope stem from the same sourceof hardness as for the correlation polytope: a direct sum structure.

The matching polytope does not admit fully-polynomial size relaxation schemes