×

zbMATH — the first resource for mathematics

Approximating \(k\)-median via pseudo-approximation. (English) Zbl 1338.90346

MSC:
90C27 Combinatorial optimization
68W25 Approximation algorithms
90B80 Discrete location and assignment
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Archer, R. Rajagopalan, and D. B. Shmoys, Lagrangian relaxation for the k-median problem: New insights and continuity properties, in Proceedings of the 11th Annual European Symposium on Algorithms, 2003, pp. 31–42. · Zbl 1266.90117
[2] V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit, Local search heuristics for k-median and facility location problems, SIAM J. Comput., 33 (2004), pp. 544–562. · Zbl 1105.68118
[3] P. Awasthi, A. Blum, and O. Sheffet, Stability yields a PTAS for k-median and k-means clustering, in Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS ’10), IEEE Computer Society, Washington, DC, 2010, pp. 309–318.
[4] P. S. Bradley, U. M. Fayyad, and O. L. Mangasarian, Mathematical programming for data mining: Formulations and challenges, INFORMS J. Comput., 11 (1998), pp. 217–238. · Zbl 0973.90096
[5] J. Byrka and K. Aardal, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM J. Comput., 39 (2010), pp. 2212–2231. · Zbl 1205.90173
[6] M. Charikar and S. Guha, Improved combinatorial algorithms for facility location problems, SIAM J. Comput., 34 (2005), pp. 803–824. · Zbl 1075.68100
[7] M. Charikar, S. Guha, E. Tardos, and D. B. Shmoys, A constant-factor approximation algorithm for the k-median problem, J. Comput. System Sci., 65 (2002), pp. 129–149. · Zbl 1023.90037
[8] M. Charikar and S. Li, A dependent LP-rounding approach for the k-median problem, in Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP ’12), Warwick, UK, 2012, pp. 194–205. · Zbl 1272.90020
[9] F. A. Chudak and D. B. Shmoys, Improved approximation algorithms for the uncapacitated facility location problem, SIAM J. Comput., 33 (2003), pp. 1–25. · Zbl 1044.90056
[10] J. Chuzhoy and Y. Rabani, Approximating k-median with non-uniform capacities, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2005, pp. 952–958. · Zbl 1297.68262
[11] S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms, J. Algorithms, 31 (1999), pp. 228–248. · Zbl 0928.68137
[12] K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM, 50 (2003), pp. 795–824. · Zbl 1325.90060
[13] K. Jain, M. Mahdian, and A. Saberi, A new greedy approach for facility location problems, in Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC ’02), ACM, New York, 2002, pp. 731–740. · Zbl 1192.90106
[14] K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, J. ACM, 48 (2001), pp. 274–296. · Zbl 1138.90417
[15] M. R. Korupolu, C. G. Plaxton, and R. Rajaraman, Analysis of a local search heuristic for facility location problems, J. Algorithms, 37 (2000), pp. 146–188. · Zbl 0962.68044
[16] A. A. Kuehn and M. J. Hamburger, A heuristic program for locating warehouses, Management Sci., 9 (1963), pp. 643–666.
[17] J. B. Lasserre, An explicit equivalent positive semidefinite program for nonlinear \textup0-1 programs, SIAM J. Optim., 12 (2002), pp. 756–769. · Zbl 1007.90046
[18] S. Li, A 1.488 approximation algorithm for the uncapacitated facility location problem, in Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP ’11), 2011, pp. 77–88. · Zbl 1334.68301
[19] J.-H. Lin and J. S. Vitter, Approximation algorithms for geometric median problems, Inform. Process. Lett., 44 (1992), pp. 245–249. · Zbl 0764.68079
[20] J.-H. Lin and J. S. Vitter, \em\(ϵ\)-approximations with minimum packing constraint violation (extended abstract), in Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (STOC ’92), ACM, New York, 1992, pp. 771–782.
[21] M. Mahdian, Y. Ye, and J. Zhang, Approximation algorithms for metric facility location problems, SIAM J. Comput., 36 (2006), pp. 411–432. · Zbl 1151.90590
[22] A. S. Manne, Plant location under economies-of-scale—Decentralization and computation, Management Sci., 11 (1964), pp. 213–235.
[23] H. D. Sherali and W. P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3 (1990), pp. 411–430. · Zbl 0712.90050
[24] D. B. Shmoys, E. Tardos, and K. Aardal, Approximation algorithms for facility location problems (extended abstract), in Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC ’97), ACM, New York, 1997, pp. 265–274. · Zbl 0962.68008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.