Bicriteria network design via iterative rounding

Piotr Krysta

doi:10.1007/11533719_20

Bicriteria network design via iterative rounding

Piotr Krysta

Research output: Contribution to journal › Conference article › peer-review

2 Scopus citations

Abstract

We study the edge-connectivity survivable network design problem with an additional linear budget constraint. We give a strongly polynomial time (3,3)-approximation algorithm for this problem, by extending a linear programming based technique of iterative rounding. Previously, a (4,4)-approximation algorithm for this problem was known. The running time of this previous algorithm is not strongly polynomial.

Original language	English (US)
Pages (from-to)	179-187
Number of pages	9
Journal	Lecture Notes in Computer Science
Volume	3595
DOIs	https://doi.org/10.1007/11533719_20
State	Published - 2005
Event	11th Annual International Conference on Computing and Combinatorics, COCOON 2005 - Kunming, China Duration: Aug 16 2005 → Aug 29 2005

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11533719_20

Cite this

@article{4e6d34a027764cd1bdcdd92bfe0fdcd5,

title = "Bicriteria network design via iterative rounding",

abstract = "We study the edge-connectivity survivable network design problem with an additional linear budget constraint. We give a strongly polynomial time (3,3)-approximation algorithm for this problem, by extending a linear programming based technique of iterative rounding. Previously, a (4,4)-approximation algorithm for this problem was known. The running time of this previous algorithm is not strongly polynomial.",

author = "Piotr Krysta",

year = "2005",

doi = "10.1007/11533719\_20",

language = "English (US)",

volume = "3595",

pages = "179--187",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "11th Annual International Conference on Computing and Combinatorics, COCOON 2005 ; Conference date: 16-08-2005 Through 29-08-2005",

}

TY - JOUR

T1 - Bicriteria network design via iterative rounding

AU - Krysta, Piotr

PY - 2005

Y1 - 2005

N2 - We study the edge-connectivity survivable network design problem with an additional linear budget constraint. We give a strongly polynomial time (3,3)-approximation algorithm for this problem, by extending a linear programming based technique of iterative rounding. Previously, a (4,4)-approximation algorithm for this problem was known. The running time of this previous algorithm is not strongly polynomial.

AB - We study the edge-connectivity survivable network design problem with an additional linear budget constraint. We give a strongly polynomial time (3,3)-approximation algorithm for this problem, by extending a linear programming based technique of iterative rounding. Previously, a (4,4)-approximation algorithm for this problem was known. The running time of this previous algorithm is not strongly polynomial.

UR - https://www.scopus.com/pages/publications/26844554099

UR - https://www.scopus.com/pages/publications/26844554099#tab=citedBy

U2 - 10.1007/11533719_20

DO - 10.1007/11533719_20

M3 - Conference article

AN - SCOPUS:26844554099

SN - 0302-9743

VL - 3595

SP - 179

EP - 187

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 11th Annual International Conference on Computing and Combinatorics, COCOON 2005

Y2 - 16 August 2005 through 29 August 2005

ER -

Bicriteria network design via iterative rounding

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this