MPI-I-97-1-006
Restricted 2-factor polytopes
Cunningham, William H. and Wang, Yaoguang
February 1997, 30 pages.
.
Status: available - back from printing
The optimal $k$-restricted 2-factor problem consists of finding,
in a complete undirected graph $K_n$, a minimum cost 2-factor
(subgraph having degree 2 at every node) with all components having more
than $k$ nodes.
The problem is a relaxation of the well-known symmetric travelling
salesman problem, and is equivalent to it when $\frac{n}{2}\leq k\leq n-1$.
We study the $k$-restricted 2-factor polytope. We present a large
class of valid inequalities, called bipartition
inequalities, and describe some of their properties; some of
these results are new even for the travelling salesman polytope.
For the case $k=3$, the triangle-free 2-factor polytope,
we derive a necessary and sufficient condition for such inequalities
to be facet inducing.
-
- Attachement: MPI-I-97-1-006.ps (325 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-006
BibTeX
@TECHREPORT{CunninghamWang97,
AUTHOR = {Cunningham, William H. and Wang, Yaoguang},
TITLE = {Restricted 2-factor polytopes},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-97-1-006},
MONTH = {February},
YEAR = {1997},
ISSN = {0946-011X},
}