A new approximation algorithm for the multilevel facility location problem

Adriana F. Gabor; Jan Kees 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 Kees C.W. van Ommeren

Mathematics

University of Twente

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

32 Scopus citations

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	British 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
State	Published - 6 Mar 2010

Keywords

Approximation algorithms
Facility location
Randomized algorithms

Access to Document

10.1016/j.dam.2009.11.007

Cite this

@article{9c749d62aa224e68a9a93bf961908ce8,

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 = "Approximation algorithms, Facility location, Randomized algorithms",

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

year = "2010",

month = mar,

day = "6",

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

language = "British 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 Kees 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 - Approximation algorithms

KW - Facility location

KW - Randomized algorithms

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

U2 - 10.1016/j.dam.2009.11.007

DO - 10.1016/j.dam.2009.11.007

M3 - Article

AN - SCOPUS:75449119640

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

Other files and links

Fingerprint

Cite this