On the H-free extension complexity of the TSP

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10368356" target="_blank" >RIV/00216208:11320/17:10368356 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/s11590-016-1029-1" target="_blank" >http://dx.doi.org/10.1007/s11590-016-1029-1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s11590-016-1029-1" target="_blank" >10.1007/s11590-016-1029-1</a>

Result language

angličtina

Original language name

On the H-free extension complexity of the TSP

Original language description

It is known that the extension complexity of the TSP polytope for the complete graph is exponential in n even if the subtour inequalities are excluded. In this article we study the polytopes formed by removing other subsets of facet-defining inequalities of the TSP polytope. In particular, we consider the case when is either the set of blossom inequalities or the simple comb inequalities. These inequalities are routinely used in cutting plane algorithms for the TSP. We show that the extension complexity remains exponential even if we exclude these inequalities. In addition we show that the extension complexity of polytope formed by all comb inequalities is exponential. For our proofs, we introduce a subclass of comb inequalities, called (h, t)-uniform inequalities, which may be of independent interest.

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

2017

Confidentiality

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

Name of the periodical

Optimization Letters

ISSN

1862-4472

e-ISSN

—

Volume of the periodical

11

Issue of the periodical within the volume

3

Country of publishing house

DE - GERMANY

Number of pages

11

Pages from-to

445-455

UT code for WoS article

000395206800001

EID of the result in the Scopus database

—