Two approximation algorithms for 3-cycle covers

Markus Bläser; Bodo Manthey

doi:10.1007/3-540-45753-4_6

Two approximation algorithms for 3-cycle covers

Markus Bläser, Bodo Manthey

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

13 Citations (Scopus)

Abstract

A cycle cover of a directed graph is a collection of node disjoint cycles such that every node is part of exactly one cycle. A k-cycle cover is a cycle cover in which every cycle has length at least k. While deciding whether a directed graph has a 2-cycle cover is solvable in polynomial time, deciding whether it has a 3-cycle cover is already NP-complete. Given a directed graph with nonnegative edge weights, a maximum weight 2-cycle cover can be computed in polynomial time, too. We call the corresponding optimization problem of finding a maximum weight 3-cycle cover Max-3-DCC. In this paper we present two polynomial time approximation algorithms for Max-3-DCC. The heavier of the 3-cycle covers computed by these algorithms has at least a fraction of ⅗ − ε, for any ε > 0, of the weight of a maximum weight 3-cycle cover. As a lower bound, we prove that Max-3-DCC is APX-complete, even if the weights fulfil the triangle inequality.

Original language	English
Title of host publication	Approximation Algorithms for Combinatorial Optimization
Subtitle of host publication	5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings
Editors	Stefano Leonardi, Klaus Jansen, Vijay Vazirani
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	40-50
Number of pages	11
ISBN (Electronic)	978-3-540-45753-4
ISBN (Print)	978-3-540-44186-1
DOIs	https://doi.org/10.1007/3-540-45753-4_6
Publication status	Published - 1 Jan 2002
Externally published	Yes
Event	5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 - Universita' di Roma "La Sapienza", Rome, Italy Duration: 17 Sept 2002 → 21 Sept 2002 Conference number: 5 http://users.diag.uniroma1.it/algo02/approx02/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2462
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002
Abbreviated title	APPROX 2002
Country/Territory	Italy
City	Rome
Period	17/09/02 → 21/09/02
Internet address	http://users.diag.uniroma1.it/algo02/approx02/

Access to Document

10.1007/3-540-45753-4_6

Cite this

Bläser, M., & Manthey, B. (2002). Two approximation algorithms for 3-cycle covers. In S. Leonardi, K. Jansen, & V. Vazirani (Eds.), Approximation Algorithms for Combinatorial Optimization: 5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings (pp. 40-50). (Lecture Notes in Computer Science; Vol. 2462). Springer. https://doi.org/10.1007/3-540-45753-4_6

Bläser, Markus ; Manthey, Bodo. / Two approximation algorithms for 3-cycle covers. Approximation Algorithms for Combinatorial Optimization: 5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings. editor / Stefano Leonardi ; Klaus Jansen ; Vijay Vazirani. Berlin, Heidelberg : Springer, 2002. pp. 40-50 (Lecture Notes in Computer Science).

@inproceedings{a202143d454a4a4e89bbd1fc88615310,

title = "Two approximation algorithms for 3-cycle covers",

abstract = "A cycle cover of a directed graph is a collection of node disjoint cycles such that every node is part of exactly one cycle. A k-cycle cover is a cycle cover in which every cycle has length at least k. While deciding whether a directed graph has a 2-cycle cover is solvable in polynomial time, deciding whether it has a 3-cycle cover is already NP-complete. Given a directed graph with nonnegative edge weights, a maximum weight 2-cycle cover can be computed in polynomial time, too. We call the corresponding optimization problem of finding a maximum weight 3-cycle cover Max-3-DCC. In this paper we present two polynomial time approximation algorithms for Max-3-DCC. The heavier of the 3-cycle covers computed by these algorithms has at least a fraction of ⅗ − ε, for any ε > 0, of the weight of a maximum weight 3-cycle cover. As a lower bound, we prove that Max-3-DCC is APX-complete, even if the weights fulfil the triangle inequality.",

author = "Markus Bl{\"a}ser and Bodo Manthey",

year = "2002",

month = jan,

day = "1",

doi = "10.1007/3-540-45753-4_6",

language = "English",

isbn = "978-3-540-44186-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "40--50",

editor = "Stefano Leonardi and Klaus Jansen and Vijay Vazirani",

booktitle = "Approximation Algorithms for Combinatorial Optimization",

address = "Germany",

note = "5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002, APPROX 2002 ; Conference date: 17-09-2002 Through 21-09-2002",

url = "http://users.diag.uniroma1.it/algo02/approx02/",

}

Bläser, M & Manthey, B 2002, Two approximation algorithms for 3-cycle covers. in S Leonardi, K Jansen & V Vazirani (eds), Approximation Algorithms for Combinatorial Optimization: 5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings. Lecture Notes in Computer Science, vol. 2462, Springer, Berlin, Heidelberg, pp. 40-50, 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002, Rome, Italy, 17/09/02. https://doi.org/10.1007/3-540-45753-4_6

Two approximation algorithms for 3-cycle covers. / Bläser, Markus; Manthey, Bodo.
Approximation Algorithms for Combinatorial Optimization: 5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings. ed. / Stefano Leonardi; Klaus Jansen; Vijay Vazirani. Berlin, Heidelberg: Springer, 2002. p. 40-50 (Lecture Notes in Computer Science; Vol. 2462).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Two approximation algorithms for 3-cycle covers

AU - Bläser, Markus

AU - Manthey, Bodo

N1 - Conference code: 5

PY - 2002/1/1

Y1 - 2002/1/1

N2 - A cycle cover of a directed graph is a collection of node disjoint cycles such that every node is part of exactly one cycle. A k-cycle cover is a cycle cover in which every cycle has length at least k. While deciding whether a directed graph has a 2-cycle cover is solvable in polynomial time, deciding whether it has a 3-cycle cover is already NP-complete. Given a directed graph with nonnegative edge weights, a maximum weight 2-cycle cover can be computed in polynomial time, too. We call the corresponding optimization problem of finding a maximum weight 3-cycle cover Max-3-DCC. In this paper we present two polynomial time approximation algorithms for Max-3-DCC. The heavier of the 3-cycle covers computed by these algorithms has at least a fraction of ⅗ − ε, for any ε > 0, of the weight of a maximum weight 3-cycle cover. As a lower bound, we prove that Max-3-DCC is APX-complete, even if the weights fulfil the triangle inequality.

AB - A cycle cover of a directed graph is a collection of node disjoint cycles such that every node is part of exactly one cycle. A k-cycle cover is a cycle cover in which every cycle has length at least k. While deciding whether a directed graph has a 2-cycle cover is solvable in polynomial time, deciding whether it has a 3-cycle cover is already NP-complete. Given a directed graph with nonnegative edge weights, a maximum weight 2-cycle cover can be computed in polynomial time, too. We call the corresponding optimization problem of finding a maximum weight 3-cycle cover Max-3-DCC. In this paper we present two polynomial time approximation algorithms for Max-3-DCC. The heavier of the 3-cycle covers computed by these algorithms has at least a fraction of ⅗ − ε, for any ε > 0, of the weight of a maximum weight 3-cycle cover. As a lower bound, we prove that Max-3-DCC is APX-complete, even if the weights fulfil the triangle inequality.

UR - http://www.scopus.com/inward/record.url?scp=84956991107&partnerID=8YFLogxK

U2 - 10.1007/3-540-45753-4_6

DO - 10.1007/3-540-45753-4_6

M3 - Conference contribution

AN - SCOPUS:84956991107

SN - 978-3-540-44186-1

T3 - Lecture Notes in Computer Science

SP - 40

EP - 50

BT - Approximation Algorithms for Combinatorial Optimization

A2 - Leonardi, Stefano

A2 - Jansen, Klaus

A2 - Vazirani, Vijay

PB - Springer

CY - Berlin, Heidelberg

T2 - 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002

Y2 - 17 September 2002 through 21 September 2002

ER -

Bläser M, Manthey B. Two approximation algorithms for 3-cycle covers. In Leonardi S, Jansen K, Vazirani V, editors, Approximation Algorithms for Combinatorial Optimization: 5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings. Berlin, Heidelberg: Springer. 2002. p. 40-50. (Lecture Notes in Computer Science). doi: 10.1007/3-540-45753-4_6

Two approximation algorithms for 3-cycle covers

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this