Approximating maximum weight cycle covers in directed graphs with weights zero and one

Share/Save/Bookmark

Bläser, Markus and Manthey, Bodo (2005) Approximating maximum weight cycle covers in directed graphs with weights zero and one. Algorithmica, 42 (2). pp. 121-139. ISSN 0178-4617

[img]PDF
Restricted to UT campus only
: Request a copy
362Kb
Abstract:A cycle cover of a graph is a spanning subgraph each node of which is part of exactly one simple cycle. A $k$-cycle cover is a cycle cover where each cycle has length at least $k$. Given a complete directed graph with edge weights zero and one, Max-$k$-DCC(0, 1) is the problem of finding a k-cycle cover with maximum weight.
We present a $\frac{2}{3}$ approximation algorithm for Max-$k$-DCC(0, 1) with running time $O(n^{5/2)}$. This algorithm yields a $\frac{4}{3}$ approximation algorithm for Min-$k$-DCC(1, 2) as well. Instances of the latter problem are complete directed graphs with edge weights one and two. The goal is to find a $k$-cycle cover with minimum weight. We particularly obtain a $\frac{2}{3}$ approximation algorithm for the asymmetric maximum traveling salesman problem with distances zero and one and a $\frac{4}{3}$ approximation algorithm for the asymmetric minimum traveling salesman problem with distances one and two.
As a lower bound, we prove that Max-$k$-DCC(0, 1) for $k \geq 3$ and Max$k$-UCC(0, 1) (finding maximum weight cycle covers in undirected graphs) for $k \geq 7$ are APX-complete.
Item Type:Article
Copyright:© 2005 Springer
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/79421
Official URL:http://dx.doi.org/10.1007/s00453-004-1131-0
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page