非表示:
キーワード:
-
要旨:
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.
