Approximation algorithms for matroid and knapsack means problems. (English) Zbl 1533.90104
Summary: In this paper, we concentrate on studying the \(k\)-means problem with a matroid or a knapsack constraint. In the matroid means problem, given an observation set and a matroid, the goal is to find a center set from the independent sets to minimize the cost. By using the linear programming (LP)-rounding technology, we obtain a constant approximation guarantee. For the knapsack means problem, we adopt a similar strategy to that of matroid means problem, whereas the difference is that we add a knapsack covering inequality to the relaxed LP in order to decrease the unbounded integrality gap.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Aggarwal, A, A Deshpande and R Kannan (2009). Adaptive sampling for \(k\)-means clustering. In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009,Berkeley, CA, USA, August 21-23, 2009. Lecture Notes in Computer Science 5687, Springer 2009, pp. 15-28. · Zbl 1254.68351 |
| [2] | Ahmadian, S, A Norouzi-Fard, O Svensson and J Ward (2017). Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. IEEE Computer Society 2017, pp. 61-72. |
| [3] | Arthur, D and Vassilvitskii, S (2007). \(k\)-means++: The advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, , January 7-9, pp. 1027-1035. · Zbl 1302.68273 |
| [4] | Charikar, M and Li, S (2012). A dependent LP-rounding approach for the \(k\)-median problem. In Proceedings of Automata, Languages, and Programming 39th International Colloquium, ICALP 2012, Warwick, UK, , July 9-13. · Zbl 1272.90020 |
| [5] | Chen, D, Li, J, Liang, H and Wang, H (2016). Matroid and knapsack center problems. Algorithmica, 75, 27-52. · Zbl 1344.68282 |
| [6] | Hajiaghayi, M, Khandekar, R and Kortsarz, G (2012). Local search algorithms for the red-blue median problem. Algorithmica, 63, 795-814. · Zbl 1262.90146 |
| [7] | Han, L, Xu, D, Li, M and Zhang, D (2018). Approximation algorithms for the robust facility leasing problem. Optimization Letters, 12, 625-637. · Zbl 1417.90102 |
| [8] | Ji, S, Xu, D, Guo, L, Li, M and Zhang, D (2020a). The seeding algorithm for spherical \(k\)-means clustering with penalties. Journal of Combinatorial Optimization, https://doi.org/10.1007/s10878-020-00569-1. · Zbl 1502.90150 |
| [9] | Ji, S, Xu, D, Li, M and Wang, Y (2020b). Approximation algorithms for two variants of correlation clustering problem. Journal of Combinatorial Optimization, https://doi.org/10.1007/s10878-020-00612-1. · Zbl 1495.90155 |
| [10] | Kale, S (2019). Small space stream summary for matroid center. In Proceedings of Approximation, Randomization, and Combinatorial Optimization., Massachusetts Institute of Technology, Cambridge, MA, USA, pp. 1-22. · Zbl 07650087 |
| [11] | Kanungo, T, Mount, DM, Netanyahu, NS, Piatko, CD, Silverman, R and Wu, AY (2004). A local search approximation algorithm for \(k\)-means clustering. Computational Geometry, 28, 89-112. · Zbl 1077.68109 |
| [12] | Krishnaswamy, R, Kumar, A, Nagarajan, V, Sabharwal, Y and Saha, Y (2011). The matroid median problem. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 1117-1130. · Zbl 1377.90076 |
| [13] | Li, M, Xu, D, Yue, J, Zhang, D and Zhang, P (2020). The seeding algorithm for \(k\)-means problem with penalties. Journal of Combinatorial Optimization, 39, 15-32. · Zbl 1434.68680 |
| [14] | Li, M (2020). The bi-criteria seeding algorithms for two variants of \(k\)-means problem. Journal of Combinatorial Optimization, https://doi.org/10.1007/s10878-020-00537-9. · Zbl 1502.90153 |
| [15] | Lloyd, S (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28, 129-137. · Zbl 0504.94015 |
| [16] | Swamy, C (2016). Improved approximation algorithms for matroid and knapsack median problems and applications. ACM Transactions on Algorithms, 12, 1-22. · Zbl 1446.68199 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
