A new approximation algorithm for the multilevel facility location problem

Adriana F. Gabor; Jan C.W. van Ommeren

doi:10.1016/j.dam.2009.11.007

A new approximation algorithm for the multilevel facility location problem

Adriana F. Gabor, Jan C.W. van Ommeren

Stochastic Operations Research

Research output: Contribution to journal › Article › Academic › peer-review

32 Citations (Scopus)

122 Downloads (Pure)

Abstract

In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.

Original language	English
Pages (from-to)	453-460
Number of pages	8
Journal	Discrete applied mathematics
Volume	158
Issue number	5
DOIs	https://doi.org/10.1016/j.dam.2009.11.007
Publication status	Published - 6 Mar 2010

Keywords

MSC-68W25
Approximation algorithms
Randomized algorithms
Facility location

Access to Document

10.1016/j.dam.2009.11.007Licence: Other

MLFLP-DAM2010Final published version, 969 KBLicence: Other

Cite this

@article{4bb5eda034114f9a891a80d656f19f6e,

title = "A new approximation algorithm for the multilevel facility location problem",

abstract = "In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.",

keywords = "MSC-68W25, Approximation algorithms, Randomized algorithms, Facility location",

author = "Gabor, {Adriana F.} and {van Ommeren}, {Jan C.W.}",

year = "2010",

month = mar,

day = "6",

doi = "10.1016/j.dam.2009.11.007",

language = "English",

volume = "158",

pages = "453--460",

journal = "Discrete applied mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - A new approximation algorithm for the multilevel facility location problem

AU - Gabor, Adriana F.

AU - van Ommeren, Jan C.W.

PY - 2010/3/6

Y1 - 2010/3/6

N2 - In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.

AB - In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.

KW - MSC-68W25

KW - Approximation algorithms

KW - Randomized algorithms

KW - Facility location

U2 - 10.1016/j.dam.2009.11.007

DO - 10.1016/j.dam.2009.11.007

M3 - Article

SN - 0166-218X

VL - 158

SP - 453

EP - 460

JO - Discrete applied mathematics

JF - Discrete applied mathematics

IS - 5

ER -

A new approximation algorithm for the multilevel facility location problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this