Name
Abstract | ||
|---|---|---|
Knapsack median is a generalization of the classic -median problem in which we replace the cardinality constraint with a knapsack constraint. It is currently known to be 32-approximable. We improve on the best known algorithms in several ways, including adding randomization and applying sparsification as a preprocessing step. The latter improvement produces the first LP for this problem with bounded integrality gap. The new algorithm obtains an approximation factor of 17.46. We also give a 3.05 approximation with small budget violation. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s00453-017-0294-4 | Algorithmica |
Keywords | DocType | Volume |
Approximation algorithm,Combinatorial optimization,Randomized algorithm,Facility-location problems | Journal | 80 |
Issue | ISSN | Citations |
4 | 0178-4617 | 1 |
PageRank | References | Authors |
0.35 | 7 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jaroslaw Byrka | 1 | 523 | 31.45 |
| Thomas Pensyl | 2 | 29 | 2.81 |
| Bartosz Rybicki | 3 | 43 | 4.80 |
| Joachim Spoerhase | 4 | 112 | 14.12 |
| Aravind Srinivasan | 5 | 3531 | 291.42 |
| Khoa Trinh | 6 | 102 | 6.32 |