{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T06:32:16Z","timestamp":1768545136740,"version":"3.49.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T00:00:00Z","timestamp":1693353600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T00:00:00Z","timestamp":1693353600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"European Research Council,European Union","award":["819416"],"award-info":[{"award-number":["819416"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s00453-023-01164-6","type":"journal-article","created":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T14:02:06Z","timestamp":1693404126000},"page":"3816-3827","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On Colorful Vertex and Edge Cover Problems"],"prefix":"10.1007","volume":"85","author":[{"given":"Sayan","family":"Bandyapadhyay","sequence":"first","affiliation":[]},{"given":"Aritra","family":"Banik","sequence":"additional","affiliation":[]},{"given":"Sujoy","family":"Bhore","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,30]]},"reference":[{"key":"1164_CR1","doi-asserted-by":"crossref","unstructured":"Anegg, G., Angelidakis, H., Kurpisz, A., Zenklusen, R.: A technique for obtaining true approximations for k-center with covering constraints. In: Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, vol. 12125, pp. 52\u201365. Springer (2020)","DOI":"10.1007\/978-3-030-45771-6_5"},{"key":"1164_CR2","doi-asserted-by":"crossref","unstructured":"Bandyapadhyay, S., Banik, A., Bhore, S. On fair covering and hitting problems. In: Kowalik, L., Pilipczuk, M., Rzazewski, P. (eds.) Graph-Theoretic Concepts in Computer Science\u201447th International Workshop, WG 2021, Warsaw, Poland, June 23\u201325, 2021, Revised Selected Papers, vol. 12911 of Lecture Notes in Computer Science, pp. 39\u201351. Springer (2021)","DOI":"10.1007\/978-3-030-86838-3_4"},{"key":"1164_CR3","unstructured":"Bandyapadhyay, S., Inamdar, T., Pai, S., Varadarajan, K.\u00a0R.: A constant approximation for colorful k-center. In: 27th Annual European Symposium on Algorithms, ESA 2019, vol. 144 of LIPIcs, pp. 12:1\u201312:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"issue":"2","key":"1164_CR4","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jagm.2000.1150","volume":"39","author":"R Bar-Yehuda","year":"2001","unstructured":"Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2), 137\u2013144 (2001)","journal-title":"J. Algorithms"},{"key":"1164_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2014.04.006","volume":"555","author":"SK Bera","year":"2014","unstructured":"Bera, S.K., Gupta, S., Kumar, A., Roy, S.: Approximation algorithms for the partition vertex cover problem. Theoret. Comput. Sci. 555, 2\u20138 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"1164_CR6","doi-asserted-by":"crossref","unstructured":"Bshouty, N.\u00a0H., Burroughs, L.: Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Annual Symposium on Theoretical Aspects of Computer Science, pp. 298\u2013308. Springer (1998)","DOI":"10.1007\/BFb0028569"},{"key":"1164_CR7","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Matroids, matchings, and fairness. In Chaudhuri, K., Sugiyama, M. (eds) The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, vol.\u00a089 of Proceedings of Machine Learning Research, pp. 2212\u20132220. PMLR (2019)"},{"key":"1164_CR8","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.endm.2017.10.038","volume":"62","author":"J Cohen","year":"2017","unstructured":"Cohen, J., Manoussakis, Y., Phong, H., Tuza, Z.: Tropical matchings in vertex-colored graphs. Electron. Notes Discrete Math. 62, 219\u2013224 (2017)","journal-title":"Electron. Notes Discrete Math."},{"key":"1164_CR9","doi-asserted-by":"crossref","unstructured":"Freeman, R., Micha, E., Shah,N.: Two-sided matching meets fair division. IJCAI (2021)","DOI":"10.24963\/ijcai.2021\/29"},{"key":"1164_CR10","unstructured":"Friggstad, Z., Rezapour, M., Salavatipour, M.\u00a0R.: Approximating connected facility location with lower and upper bounds via lp rounding. In: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"issue":"1","key":"1164_CR11","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"key":"1164_CR12","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness (1979)"},{"key":"1164_CR13","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Jones, M.: On separating points by lines. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp 918\u2013932. SIAM (2018)","DOI":"10.1137\/1.9781611975031.59"},{"key":"1164_CR14","unstructured":"Inamdar, T., Varadarajan, K.\u00a0R.: On the partition set cover problem. CoRR arxiv:1809.06506 (2018)"},{"key":"1164_CR15","doi-asserted-by":"crossref","unstructured":"Jia, X., Sheth, K., Svensson, O.: Fair colorful k-center clustering. In: Integer Programming and Combinatorial Optimization\u201421st International Conference, IPCO 2020, vol. 12125, pp. 209\u2013222. Springer (2020)","DOI":"10.1007\/978-3-030-45771-6_17"},{"issue":"2","key":"1164_CR16","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s00199-004-0602-5","volume":"27","author":"B Klaus","year":"2006","unstructured":"Klaus, B., Klijn, F.: Procedurally fair and stable matching. Econ. Theor. 27(2), 431\u2013447 (2006)","journal-title":"Econ. Theor."},{"key":"1164_CR17","doi-asserted-by":"crossref","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, pp. 646\u2013659. ACM (2018)","DOI":"10.1145\/3188745.3188882"},{"key":"1164_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977152","volume-title":"Iterative Methods in Combinatorial Optimization","author":"LC Lau","year":"2011","unstructured":"Lau, L.C., Ravi, R., Singh, M.: Iterative Methods in Combinatorial Optimization, vol. 46. Cambridge University Press, Cambridge (2011)"},{"key":"1164_CR19","doi-asserted-by":"crossref","unstructured":"Li. S.: Approximating capacitated k-median with (1+$$\\epsilon $$) k open facilities. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 786\u2013796. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch56"},{"issue":"2","key":"1164_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2983633","volume":"13","author":"S Li","year":"2017","unstructured":"Li, S.: On uniform capacitated k-median beyond the natural LP relaxation. ACM Trans. Algorithm (TALG) 13(2), 1\u201318 (2017)","journal-title":"ACM Trans. Algorithm (TALG)"},{"issue":"5","key":"1164_CR21","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P Slavik","year":"1997","unstructured":"Slavik, P.: Improved performance of the greedy algorithm for partial cover. Inf. Process. Lett. 64(5), 251\u2013254 (1997)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01164-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01164-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01164-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,10]],"date-time":"2023-11-10T13:05:48Z","timestamp":1699621548000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01164-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,30]]},"references-count":21,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1164"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01164-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,30]]},"assertion":[{"value":"16 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We wish to confirm that there are no known conflicts of interest associated with this publication and there has been no significant financial support for this work that could have influenced its outcome. We confirm that the manuscript has been read and approved by all named authors and that there are no other persons who satisfied the criteria for authorship but are not listed. We further confirm that the order of authors listed in the manuscript has been approved by all of us. We confirm that we have given due consideration to the protection of intellectual property associated with this work and that there are no impediments to publication, including the timing of publication, with respect to intellectual property.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}