A generalization of extension complexity that captures P

DOI10.1016/J.IPL.2015.02.005MaRDI QIDQ2345857zbMATH OpenOpenAlexFDO

Authors Hans Raj Tiwary, David Avis

Publication date 21 May 2015

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.5950

zbMATH Keywords

combinatorial problemscomputational complexityextended formulationsextension complexitylinear programminglower boundspolytopestheory of computation

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Combinatorial optimization (90C27)

Abstract: In this paper we propose a generalization of the extension complexity of a polyhedron $Q$. On the one hand it is general enough so that all problems in $P$ can be formulated as linear programs with polynomial size extension complexity. On the other hand it still allows non-polynomial lower bounds to be proved for $NP$-hard problems independently of whether or not $P=NP$. The generalization, called $H$-free extension complexity, allows for a set of valid inequalities $H$ to be excluded in computing the extension complexity of $Q$. We give results on the $H$-free extension complexity of hard matching problems (when $H$ are the odd set inequalities) and the traveling salesman problem (when $H$ are the subtour elimination constraints).

Recommendations

• On the \({\mathcal {H}}\)-free extension complexity of the TSP

Cites work

• A note on the extension complexity of the knapsack polytope
• Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
• Edge Dominating Sets in Graphs
• Expressing combinatorial optimization problems by linear programs
• Extended formulations in combinatorial optimization
• Induced matchings
• Linear vs. semidefinite extended formulations
• Matching theory
• Maximum matching and a polyhedron with 0,1-vertices
• NP-completeness of some generalizations of the maximum matching problem
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(6)

• New limits of treewidth-based tractability in optimization
• Compact linear programs for 2SAT
• Polynomial size linear programs for problems in \textsc{P}
• scientific article; zbMATH DE number 17551 (Why is no real title available?)
• On the \({\mathcal {H}}\)-free extension complexity of the TSP
• Binary cyclic transversal polytopes

This page was built for publication: A generalization of extension complexity that captures P

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345857)