A fast $$(2 + \frac{2}{7})$$-approximation algorithm for capacitated cycle covering
研究了带容量约束的环覆盖问题，每个环最多服务一个单位的顶点需求，目标是最小化总长度和环数的线性组合。提出一个贪心加后处理的算法，达到(2+2/7)近似比，并证明分析紧且松弛有2+ε下界。
Abstract We consider the capacitated cycle covering problem : given an undirected, complete graph G with metric edge lengths and demands on the vertices, we want to cover the vertices with vertex-disjoint cycles, each serving a demand of at most one. The objective is to minimize a linear combination of the total length and the number of cycles. This problem is closely related to the capacitated vehicle routing problem (CVRP) and other cycle cover problems such as min-max cycle cover and bounded cycle cover. We show that a greedy algorithm followed by a post-processing step yields a $$(2 + \frac{2}{7})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mfrac> <mml:mn>2</mml:mn> <mml:mn>7</mml:mn> </mml:mfrac> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximation for this problem by comparing the solution to a polymatroid relaxation. We also show that the analysis of our algorithm is tight and provide a $$2 + \epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> lower bound for the relaxation.