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

Keywords

  • Facility location
  • Facility location problem
  • Dual solution
  • Demand point
  • Central path

Fingerprint Dive into the research topics of 'A simple dual ascent algorithm for the multilevel facility location problem'. Together they form a unique fingerprint.

  • 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