A simple dual ascent algorithm for the multilevel facility location problem

Adriana Bumb, Walter Kern

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We present a simple dual ascent method for the multilevel facility location problem which finds a solution within 6 times the optimum for the uncapacitated case and within 12 times the optimum for the capacitated one. The algorithm is deterministic and based on the primal-dual technique.
Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques
EditorsMichel Goemans, Klaus Jansen, José D.P. Rolim, Luca Trevisan
Place of PublicationBerkeley, CA, USA
PublisherSpringer
Pages55-62
ISBN (Electronic)978-3-540-44666-8
ISBN (Print)978-3-540-42470-3
DOIs
Publication statusPublished - 2001
Event4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 - Berkeley, United States
Duration: 18 Aug 200120 Aug 2001
Conference number: 4

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume2129
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001
Abbreviated titleAPPROX
CountryUnited States
CityBerkeley
Period18/08/0120/08/01

Fingerprint

Facility Location Problem
Ascent
Primal-dual

Keywords

  • IR-79992
  • METIS-202722

Cite this

Bumb, A., & Kern, W. (2001). A simple dual ascent algorithm for the multilevel facility location problem. In M. Goemans, K. Jansen, J. D. P. Rolim, & L. Trevisan (Eds.), Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (pp. 55-62). (Lecture notes in computer science; Vol. 2129). Berkeley, CA, USA: Springer. https://doi.org/10.1007/3-540-44666-4_10
Bumb, Adriana ; Kern, Walter . / A simple dual ascent algorithm for the multilevel facility location problem. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. editor / Michel Goemans ; Klaus Jansen ; José D.P. Rolim ; Luca Trevisan. Berkeley, CA, USA : Springer, 2001. pp. 55-62 (Lecture notes in computer science).
@inproceedings{ee7b4b0f807c4167b2ef82abc36fcd26,
title = "A simple dual ascent algorithm for the multilevel facility location problem",
abstract = "We present a simple dual ascent method for the multilevel facility location problem which finds a solution within 6 times the optimum for the uncapacitated case and within 12 times the optimum for the capacitated one. The algorithm is deterministic and based on the primal-dual technique.",
keywords = "IR-79992, METIS-202722",
author = "Adriana Bumb and Walter Kern",
year = "2001",
doi = "10.1007/3-540-44666-4_10",
language = "English",
isbn = "978-3-540-42470-3",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "55--62",
editor = "Michel Goemans and Klaus Jansen and Rolim, {Jos{\'e} D.P.} and Luca Trevisan",
booktitle = "Approximation, Randomization, and Combinatorial Optimization",

}

Bumb, A & Kern, W 2001, A simple dual ascent algorithm for the multilevel facility location problem. in M Goemans, K Jansen, JDP Rolim & L Trevisan (eds), Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. Lecture notes in computer science, vol. 2129, Springer, Berkeley, CA, USA, pp. 55-62, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001, Berkeley, United States, 18/08/01. https://doi.org/10.1007/3-540-44666-4_10

A simple dual ascent algorithm for the multilevel facility location problem. / Bumb, Adriana; Kern, Walter .

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. ed. / Michel Goemans; Klaus Jansen; José D.P. Rolim; Luca Trevisan. Berkeley, CA, USA : Springer, 2001. p. 55-62 (Lecture notes in computer science; Vol. 2129).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - A simple dual ascent algorithm for the multilevel facility location problem

AU - Bumb, Adriana

AU - Kern, Walter

PY - 2001

Y1 - 2001

N2 - We present a simple dual ascent method for the multilevel facility location problem which finds a solution within 6 times the optimum for the uncapacitated case and within 12 times the optimum for the capacitated one. The algorithm is deterministic and based on the primal-dual technique.

AB - We present a simple dual ascent method for the multilevel facility location problem which finds a solution within 6 times the optimum for the uncapacitated case and within 12 times the optimum for the capacitated one. The algorithm is deterministic and based on the primal-dual technique.

KW - IR-79992

KW - METIS-202722

U2 - 10.1007/3-540-44666-4_10

DO - 10.1007/3-540-44666-4_10

M3 - Conference contribution

SN - 978-3-540-42470-3

T3 - Lecture notes in computer science

SP - 55

EP - 62

BT - Approximation, Randomization, and Combinatorial Optimization

A2 - Goemans, Michel

A2 - Jansen, Klaus

A2 - Rolim, José D.P.

A2 - Trevisan, Luca

PB - Springer

CY - Berkeley, CA, USA

ER -

Bumb A, Kern W. A simple dual ascent algorithm for the multilevel facility location problem. In Goemans M, Jansen K, Rolim JDP, Trevisan L, editors, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. Berkeley, CA, USA: Springer. 2001. p. 55-62. (Lecture notes in computer science). https://doi.org/10.1007/3-540-44666-4_10