Paper Info
Title
Improved approximation algorithm for k-level UFL with penalties, a simplistic view on randomizing the scaling parameter.
Abstract
The state of the art in approximation algorithms for facility location problems are complicated combinations of various techniques. In particular, the currently best 1.488-approximation algorithm for the uncapacitated facility location (UFL) problem by Shi Li is presented as a result of a non-trivial randomization of a certain scaling parameter in the LP-rounding algorithm by Chudak and Shmoys combined with a primal-dual algorithm of Jain et al. In this paper we first give a simple interpretation of this randomization process in terms of solving an auxiliary (factor revealing) LP. Then, armed with this simple view point, we exercise the randomization on a more complicated algorithm for the k-level version of the problem with penalties in which the planner has the option to pay a penalty instead of connecting chosen clients, which results in an improved approximation algorithm.
Year
DOI
Venue
2013
10.1007/978-3-319-08001-7_8
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
8447
0302-9743
Citations 
PageRank 
References 
2
0.39
18
Authors
3
Name
Order
Citations
PageRank
Jaroslaw Byrka152331.45
Shanfei Li251.45
Bartosz Rybicki3434.80