Publikace na Matematicko-fyzikální fakulta |
2015
Abstrakt
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).