Cycle Cover with Short Cycles

Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni

Abstract

Cycle covering is a well-studied problem in computer science. In this paper, we develop approximation algorithms for variants of cycle covering problems which bound the size and/or length of the covering cycles. In particular, we give a (1+ln 2)-approximation for the lane covering problem [3,4] in weighted graphs with metric lengths on the edges and an O(ln k) approximation for the bounded cycle cover problem [9] with cycle-size bound k in uniform graphs. Our techniques are based on interpreting a greedy algorithm (proposed and empirically evaluated by Ergun et al. [3,4]) as a dual-fitting algorithm. We then find the approximation factor by bounding the solution of a factor-revealing non-linear program. These are the first non-trivial approximation algorithms for these problems. We show that our analysis is tight for the greedy algorithm, and change the process of the dual-fitting algorithm to improve the factor for small cycle bounds. Finally, we prove that variants of the cycle cover problem which bound cycle size or length are APX-hard.
BibTeX
@inproceedings{immorlica2005cycle,
  author = {Nicole Immorlica and Mohammad Mahdian and Vahab S. Mirrokni},
  title = {{Cycle Cover with Short Cycles}},
  booktitle = {STACS},
  year = {2005},
  doi = {10.1007/978-3-540-31856-9\_53},
}

Loading related content...

Figure