{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:48:34Z","timestamp":1774421314296,"version":"3.50.1"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,1,29]],"date-time":"2018-01-29T00:00:00Z","timestamp":1517184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NCN","award":["2012\/07\/N\/ST6\/03068"],"award-info":[{"award-number":["2012\/07\/N\/ST6\/03068"]}]},{"name":"NSF Awards","award":["CNS 1010789 and CCF 1422569"],"award-info":[{"award-number":["CNS 1010789 and CCF 1422569"]}]},{"name":"Adobe, Inc"},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["DEC- 2012\/07\/B\/ST6\/01534"],"award-info":[{"award-number":["DEC- 2012\/07\/B\/ST6\/01534"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF Awards","award":["CNS 1010789 and CCF 1422569"],"award-info":[{"award-number":["CNS 1010789 and CCF 1422569"]}]},{"name":"NSF Awards","award":["CNS 1010789 and CCF 1422569"],"award-info":[{"award-number":["CNS 1010789 and CCF 1422569"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00453-017-0294-4","type":"journal-article","created":{"date-parts":[[2018,1,29]],"date-time":"2018-01-29T14:23:55Z","timestamp":1517235835000},"page":"1093-1114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["An Improved Approximation Algorithm for Knapsack Median Using Sparsification"],"prefix":"10.1007","volume":"80","author":[{"given":"Jaros\u0142aw","family":"Byrka","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Pensyl","sequence":"additional","affiliation":[]},{"given":"Bartosz","family":"Rybicki","sequence":"additional","affiliation":[]},{"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[]},{"given":"Khoa","family":"Trinh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,1,29]]},"reference":[{"key":"294_CR1","doi-asserted-by":"crossref","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for k-median, and positive correlation in budgeted optimization. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 737\u2013756 (2015)","DOI":"10.1137\/1.9781611973730.50"},{"key":"294_CR2","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. In: ACM Symposium on Theory of Computing (STOC), ACM. pp. 1\u201310 (1999)","DOI":"10.1145\/301250.301257"},{"key":"294_CR3","doi-asserted-by":"crossref","unstructured":"Charikar, M., Li, S.: A dependent LP-rounding approach for the k-median problem. In: Automata, Languages, and Programming (ICALP), pp. 194\u2013205 (2012)","DOI":"10.1007\/978-3-642-31594-7_17"},{"issue":"6","key":"294_CR4","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"issue":"2","key":"294_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$$ 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"},{"key":"294_CR6","doi-asserted-by":"crossref","unstructured":"Krishnaswamy, R., Kumar, A., Nagarajan, V., Sabharwal, Y., Saha, B.: The matroid median problem. In: Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM. pp. 1117\u20131130 (2011)","DOI":"10.1137\/1.9781611973082.84"},{"key":"294_CR7","doi-asserted-by":"crossref","unstructured":"Kumar, A.: Constant factor approximation algorithm for the knapsack median problem. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM. pp. 824\u2013832 (2012)","DOI":"10.1137\/1.9781611973099.66"},{"key":"294_CR8","doi-asserted-by":"crossref","unstructured":"Li, S., Svensson, O.: Approximating $$k$$ k -median via pseudo-approximation. In: STOC, pp. 901\u2013910 (2013)","DOI":"10.1145\/2488608.2488723"},{"key":"294_CR9","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer Science & Business Media, New York (2003)"},{"key":"294_CR10","first-page":"403","volume":"28","author":"C Swamy","year":"2014","unstructured":"Swamy, C.: Improved approximation algorithms for matroid and knapsack median problems and applications. ACM Trans. Algorithms 28, 403\u2013418 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"294_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0294-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0294-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0294-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T22:37:47Z","timestamp":1589841467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0294-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,29]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["294"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0294-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,29]]},"assertion":[{"value":"31 August 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}