{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:48:47Z","timestamp":1774421327808,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T00:00:00Z","timestamp":1720569600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T00:00:00Z","timestamp":1720569600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1907820"],"award-info":[{"award-number":["CCF-1907820"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF1955785"],"award-info":[{"award-number":["CCF1955785"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2006953"],"award-info":[{"award-number":["CCF-2006953"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1824303"],"award-info":[{"award-number":["CCF-1824303"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1845146"],"award-info":[{"award-number":["CCF-1845146"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1733873"],"award-info":[{"award-number":["CCF-1733873"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1938909"],"award-info":[{"award-number":["CMMI-1938909"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>This paper considers approximation algorithms for generalized <jats:italic>k<\/jats:italic>-median problems. These problems can be informally described as <jats:italic>k<\/jats:italic>-median with a constant number of extra constraints, and includes <jats:italic>k<\/jats:italic>-median with outliers, and knapsack median. Our first contribution is a pseudo-approximation algorithm for generalized <jats:italic>k<\/jats:italic>-median that outputs a 6.387-approximate solution, with a constant number of fractional variables. The algorithm builds on the iterative rounding framework introduced by Krishnaswamy, Li, and Sandeep for <jats:italic>k<\/jats:italic>-median with outliers as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). The main technical innovation is allowing richer constraint sets in the iterative rounding and using the structure of the resulting extreme points. Using our pseudo-approximation algorithm, we give improved approximation algorithms for <jats:italic>k<\/jats:italic>-median with outliers and knapsack median. This involves combining our pseudo-approximation with pre- and post-processing steps to round a constant number of fractional variables at a small increase in cost. Our algorithms achieve approximation ratios <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$6.994 + \\epsilon $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>6.994<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03f5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> and <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$6.387 + \\epsilon $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>6.387<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03f5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> for <jats:italic>k<\/jats:italic>-median with outliers and knapsack median, respectively. These improve on the best-known approximation ratio <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$7.081 + \\epsilon $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>7.081<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03f5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> for both problems as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018).<\/jats:p>","DOI":"10.1007\/s10107-024-02119-7","type":"journal-article","created":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T11:02:10Z","timestamp":1720609330000},"page":"581-634","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Structural iterative rounding for generalized k-median problems"],"prefix":"10.1007","volume":"212","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5037-4885","authenticated-orcid":false,"given":"Rudy","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,10]]},"reference":[{"key":"2119_CR1","doi-asserted-by":"publisher","unstructured":"Gupta, A., Moseley, B., Zhou, R.: Structural iterative rounding for generalized k-median problems. In: 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.77","DOI":"10.4230\/LIPIcs.ICALP.2021.77"},{"key":"2119_CR2","doi-asserted-by":"publisher","unstructured":"Krishnaswamy, R., Li, S., Sandeep, S.: Constant approximation for k-median and k-means with outliers via iterative rounding. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 646\u2013659. https:\/\/doi.org\/10.1145\/3188745.3188882","DOI":"10.1145\/3188745.3188882"},{"issue":"2","key":"2119_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/2981561","volume":"13","author":"J Byrka","year":"2017","unstructured":"Byrka, J., Pensyl, T.W., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms 13(2), 23\u201312331 (2017). https:\/\/doi.org\/10.1145\/2981561","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"2119_CR4","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1137\/130938645","volume":"45","author":"S Li","year":"2016","unstructured":"Li, S., Svensson, O.: Approximating k-median via pseudo-approximation. SIAM J. Comput. 45(2), 530\u2013547 (2016). https:\/\/doi.org\/10.1137\/130938645","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2119_CR5","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM 48(2), 274\u2013296 (2001). https:\/\/doi.org\/10.1145\/375827.375845","journal-title":"J. ACM"},{"issue":"3","key":"2119_CR6","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544\u2013562 (2004). https:\/\/doi.org\/10.1137\/S0097539702416402","journal-title":"SIAM J. Comput."},{"key":"2119_CR7","unstructured":"Li, S., Guo, X.: Distributed $$ k $$-clustering for data with heavy noise. In: Advances in Neural Information Processing Systems, pp. 7838\u20137846. (2018)"},{"key":"2119_CR8","unstructured":"Malkomes, G., Kusner, M., Chen, W., Weinberger, K., Moseley, B.: Fast distributed $$k$$-center clustering with outliers on massive data. In: NIPS, pp. 1063\u20131071. (2015)"},{"key":"2119_CR9","doi-asserted-by":"crossref","unstructured":"Guha, S., Li, Y., Zhang, Q.: Distributed partial clustering. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 143\u2013152 (2017). ACM","DOI":"10.1145\/3087556.3087568"},{"issue":"3","key":"2119_CR10","first-page":"515","volume":"15","author":"S Guha","year":"2003","unstructured":"Guha, S., Meyerson, A., Mishra, N., Motwani, R., O\u2019Callaghan, L.: Clustering data streams: Theory and practice. TKDE 15(3), 515\u2013528 (2003)","journal-title":"TKDE"},{"key":"2119_CR11","unstructured":"Im, S., Qaem, M.M., Moseley, B., Sun, X., Zhou, R.: Fast noise removal for k-means clustering. In: The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], pp. 456\u2013466. (2020)"},{"key":"2119_CR12","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Grandoni, F., Lee, E., Schwiegelshohn, C.: Breaching the 2 LMP approximation barrier for facility location with applications to k-median. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pp. 940\u2013986","DOI":"10.1137\/1.9781611977554.ch37"},{"key":"2119_CR13","doi-asserted-by":"publisher","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing. STOC \u201902, pp. 731\u2013740. ACM, New York, NY, USA (2002). https:\/\/doi.org\/10.1145\/509907.510012","DOI":"10.1145\/509907.510012"},{"key":"2119_CR14","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Kosaraju, S.R. (ed.) Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, pp. 642\u2013651. ACM\/SIAM, Washington (2001)"},{"issue":"2","key":"2119_CR15","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1287\/moor.2014.0678","volume":"40","author":"R Krishnaswamy","year":"2015","unstructured":"Krishnaswamy, R., Kumar, A., Nagarajan, V., Sabharwal, Y., Saha, B.: Facility location with matroid or knapsack constraints. Math. Oper. Res. 40(2), 446\u2013459 (2015). https:\/\/doi.org\/10.1287\/moor.2014.0678","journal-title":"Math. Oper. Res."},{"issue":"4","key":"2119_CR16","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1007\/s00453-017-0294-4","volume":"80","author":"J Byrka","year":"2018","unstructured":"Byrka, J., Pensyl, T.W., Rybicki, B., Spoerhase, J., Srinivasan, A., Trinh, K.: An improved approximation algorithm for knapsack median using sparsification. Algorithmica 80(4), 1093\u20131114 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0294-4","journal-title":"Algorithmica"},{"issue":"2","key":"2119_CR17","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/3301446","volume":"15","author":"Z Friggstad","year":"2019","unstructured":"Friggstad, Z., Khodamoradi, K., Rezapour, M., Salavatipour, M.R.: Approximation schemes for clustering with outliers. ACM Trans. Algorithms 15(2), 26\u201312626 (2019). https:\/\/doi.org\/10.1145\/3301446","journal-title":"ACM Trans. Algorithms"},{"key":"2119_CR18","unstructured":"Chen, K.: A constant factor approximation algorithm for $$k$$-median clustering with outliers. In: SODA, pp. 826\u2013835. (2008)"},{"issue":"1\u20132","key":"2119_CR19","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s10107-013-0703-7","volume":"146","author":"F Grandoni","year":"2014","unstructured":"Grandoni, F., Ravi, R., Singh, M., Zenklusen, R.: New approaches to multi-objective optimization. Math. Program. 146(1\u20132), 525\u2013554 (2014). https:\/\/doi.org\/10.1007\/s10107-013-0703-7","journal-title":"Math. Program."},{"key":"2119_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2022.106272","volume":"177","author":"S Deng","year":"2022","unstructured":"Deng, S.: On clustering with discounts. Inf. Process. Lett. 177, 106272 (2022). https:\/\/doi.org\/10.1016\/j.ipl.2022.106272","journal-title":"Inf. Process. Lett."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02119-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02119-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02119-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:03:06Z","timestamp":1750176186000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02119-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,10]]},"references-count":20,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["2119"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02119-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,10]]},"assertion":[{"value":"3 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}