Primal-dual approximation algorithms for node-weighted network design in planar graphs

Piotr Berman; Grigory Yaroslavtsev

doi:10.1007/978-3-642-32512-0_5

Primal-dual approximation algorithms for node-weighted network design in planar graphs

Piotr Berman, Grigory Yaroslavtsev

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

13 Scopus citations

Abstract

We present primal-dual algorithms which give a 2.4 approximation for a class of node-weighted network design problems in planar graphs, introduced by Demaine, Hajiaghayi and Klein (ICALP'09). This class includes Node-Weighted Steiner Forest problem studied recently by Moldenhauer (ICALP'11) and other node-weighted problems in planar graphs that can be expressed using (0,1)-proper functions introduced by Goemans and Williamson. We show that these problems can be equivalently formulated as feedback vertex set problems and analyze approximation factors guaranteed by different violation oracles within the primal-dual framework developed by Goemans and Williamson.

Original language	English (US)
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings
Pages	50-60
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-32512-0_5
State	Published - 2012
Event	15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012 - Cambridge, MA, United States Duration: Aug 15 2012 → Aug 17 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7408 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012
Country/Territory	United States
City	Cambridge, MA
Period	8/15/12 → 8/17/12

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-32512-0_5

Cite this

Berman, P., & Yaroslavtsev, G. (2012). Primal-dual approximation algorithms for node-weighted network design in planar graphs. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings (pp. 50-60). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7408 LNCS). https://doi.org/10.1007/978-3-642-32512-0_5

Berman, Piotr ; Yaroslavtsev, Grigory. / Primal-dual approximation algorithms for node-weighted network design in planar graphs. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. 2012. pp. 50-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6ada6c5e6c3940f593075b4dae12caf4,

title = "Primal-dual approximation algorithms for node-weighted network design in planar graphs",

abstract = "We present primal-dual algorithms which give a 2.4 approximation for a class of node-weighted network design problems in planar graphs, introduced by Demaine, Hajiaghayi and Klein (ICALP'09). This class includes Node-Weighted Steiner Forest problem studied recently by Moldenhauer (ICALP'11) and other node-weighted problems in planar graphs that can be expressed using (0,1)-proper functions introduced by Goemans and Williamson. We show that these problems can be equivalently formulated as feedback vertex set problems and analyze approximation factors guaranteed by different violation oracles within the primal-dual framework developed by Goemans and Williamson.",

author = "Piotr Berman and Grigory Yaroslavtsev",

note = "Funding Information: G.Y. is supported by NSF / CCF CAREER award 0845701 and by College of Engineering Fellowship.; 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012 ; Conference date: 15-08-2012 Through 17-08-2012",

year = "2012",

doi = "10.1007/978-3-642-32512-0_5",

language = "English (US)",

isbn = "9783642325113",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "50--60",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

}

Berman, P & Yaroslavtsev, G 2012, Primal-dual approximation algorithms for node-weighted network design in planar graphs. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7408 LNCS, pp. 50-60, 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012, Cambridge, MA, United States, 8/15/12. https://doi.org/10.1007/978-3-642-32512-0_5

Primal-dual approximation algorithms for node-weighted network design in planar graphs. / Berman, Piotr; Yaroslavtsev, Grigory.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. 2012. p. 50-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7408 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Primal-dual approximation algorithms for node-weighted network design in planar graphs

AU - Berman, Piotr

AU - Yaroslavtsev, Grigory

N1 - Funding Information: G.Y. is supported by NSF / CCF CAREER award 0845701 and by College of Engineering Fellowship.

PY - 2012

Y1 - 2012

N2 - We present primal-dual algorithms which give a 2.4 approximation for a class of node-weighted network design problems in planar graphs, introduced by Demaine, Hajiaghayi and Klein (ICALP'09). This class includes Node-Weighted Steiner Forest problem studied recently by Moldenhauer (ICALP'11) and other node-weighted problems in planar graphs that can be expressed using (0,1)-proper functions introduced by Goemans and Williamson. We show that these problems can be equivalently formulated as feedback vertex set problems and analyze approximation factors guaranteed by different violation oracles within the primal-dual framework developed by Goemans and Williamson.

AB - We present primal-dual algorithms which give a 2.4 approximation for a class of node-weighted network design problems in planar graphs, introduced by Demaine, Hajiaghayi and Klein (ICALP'09). This class includes Node-Weighted Steiner Forest problem studied recently by Moldenhauer (ICALP'11) and other node-weighted problems in planar graphs that can be expressed using (0,1)-proper functions introduced by Goemans and Williamson. We show that these problems can be equivalently formulated as feedback vertex set problems and analyze approximation factors guaranteed by different violation oracles within the primal-dual framework developed by Goemans and Williamson.

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

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

U2 - 10.1007/978-3-642-32512-0_5

DO - 10.1007/978-3-642-32512-0_5

M3 - Conference contribution

AN - SCOPUS:84865285468

SN - 9783642325113

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 50

EP - 60

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012

Y2 - 15 August 2012 through 17 August 2012

ER -

Berman P, Yaroslavtsev G. Primal-dual approximation algorithms for node-weighted network design in planar graphs. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. 2012. p. 50-60. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-32512-0_5

Primal-dual approximation algorithms for node-weighted network design in planar graphs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this