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

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

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:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page