论文标题
改善$ t $ tours的最佳奇异基督油
Improving on Best-of-Many-Christofides for $T$-tours
论文作者
论文摘要
$ t $ -TOR问题是TSP和PATH TSP的自然概括。给定图形$ g =（v，e）$，边缘成本$ c：e \ to \ to \ mathbb {r} _ {\ ge 0} $，均匀的基数set $ t \ subseteq v $，我们想计算最低cost $ t $ t $ - join连接所有$ g $ $ g $的$ g $（以及可能包含的平行edges）。 在本文中，我们给出了$ \ frac {11} {7} $ - $ t $ - toR问题的近似值，并证明标准LP放松的整体率最多是$ \ frac {11} {7} {7} $。尽管特殊案例路径TSP取得了很大进展，但对于一般$ t $ - tours，这是Sebő对最佳奇异 - 克里斯托弗斯算法的分析的第一个改进（SEBő[2013]）。
The $T$-tour problem is a natural generalization of TSP and Path TSP. Given a graph $G=(V,E)$, edge cost $c: E \to \mathbb{R}_{\ge 0}$, and an even cardinality set $T\subseteq V$, we want to compute a minimum-cost $T$-join connecting all vertices of $G$ (and possibly containing parallel edges). In this paper we give an $\frac{11}{7}$-approximation for the $T$-tour problem and show that the integrality ratio of the standard LP relaxation is at most $\frac{11}{7}$. Despite much progress for the special case Path TSP, for general $T$-tours this is the first improvement on Sebő's analysis of the Best-of-Many-Christofides algorithm (Sebő [2013]).
