| | |
| | |
Stat |
Members: 3645 Articles: 2'500'096 Articles rated: 2609
19 April 2024 |
|
| | | |
|
Article overview
| |
|
On the Factor Revealing LP Approach for Facility Location with Penalties | Xian Qiu
; Walter Kern
; | Date: |
31 Jan 2016 | Abstract: | We consider the uncapacitated facility location problem with (linear) penalty
function and show that a modified JMS algorithm, combined with a randomized LP
rounding technique due to Byrka-Aardal[1], Li[14] and Li et al.[16] yields
1.488 approximation, improving the factor 1.5148 due to Li et al.[16]. This
closes the current gap between the classical facility location problem and this
penalized variant. Main ingredient is a straightforward adaptation of the JMS
algorithm to the penalty setting plus a consistent use of the upper bounding
technique for factor revealing LPs due to Fernandes et al.[7]. In contrast to
the bounds in [12], our factor revealing LP is monotone. | Source: | arXiv, 1602.0192 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |