A simple dual ascent algorithm for the multilevel facility location problem

Adriana Bumb; Walter  Kern

doi:10.1007/3-540-44666-4_10

A simple dual ascent algorithm for the multilevel facility location problem

Adriana Bumb, Walter Kern

Discrete Mathematics and Mathematical Programming

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

8 Downloads (Pure)

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 language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques
Editors	Michel Goemans, Klaus Jansen, José D.P. Rolim, Luca Trevisan
Place of Publication	Berkeley, CA, USA
Publisher	Springer
Pages	55-62
ISBN (Electronic)	978-3-540-44666-8
ISBN (Print)	978-3-540-42470-3
DOIs	https://doi.org/10.1007/3-540-44666-4_10
Publication status	Published - 2001
Event	4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 - Berkeley, United States Duration: 18 Aug 2001 → 20 Aug 2001 Conference number: 4

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	2129
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001
Abbreviated title	APPROX
Country/Territory	United States
City	Berkeley
Period	18/08/01 → 20/08/01

Keywords

Facility location
Facility location problem
Dual solution
Demand point
Central path

Access to Document

10.1007/3-540-44666-4_10

Cite this

@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 = "Facility location, Facility location problem, Dual solution, Demand point, Central path",

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",

address = "Germany",

note = "4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001, APPROX ; Conference date: 18-08-2001 Through 20-08-2001",

}

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, California, 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 proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Bumb, Adriana

AU - Kern, Walter

N1 - Conference code: 4

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 - Facility location

KW - Facility location problem

KW - Dual solution

KW - Demand point

KW - Central path

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

T2 - 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001

Y2 - 18 August 2001 through 20 August 2001

ER -

A simple dual ascent algorithm for the multilevel facility location problem

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this