{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:03Z","timestamp":1779174843351,"version":"3.51.4"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T00:00:00Z","timestamp":1670371200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T00:00:00Z","timestamp":1670371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,5]]},"DOI":"10.1007\/s00453-022-01072-1","type":"journal-article","created":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T07:03:22Z","timestamp":1670396602000},"page":"1287-1331","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Maximizing Coverage While Ensuring Fairness: A Tale of Conflicting Objectives"],"prefix":"10.1007","volume":"85","author":[{"given":"Abolfazl","family":"Asudeh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tanya","family":"Berger-Wolf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5614-5477","authenticated-orcid":false,"given":"Bhaskar","family":"DasGupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,7]]},"reference":[{"key":"1072_CR1","doi-asserted-by":"crossref","unstructured":"Ageev, A., Sviridenko, M.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3), 307\u2013328 (2004)","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"1072_CR2","unstructured":"Angwin, J., Parris, T.: Facebook lets advertisers exclude users by race, Propublica, October 28, 2016. http:\/\/www.propublica.org\/article\/facebook-lets-advertisers-exclude-users-by-race"},{"key":"1072_CR3","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.dam.2013.05.015","volume":"165","author":"N Apollonio","year":"2014","unstructured":"Apollonio, N., Simeone, B.: The maximum vertex coverage problem on bipartite graphs. Discrete Appl. Math. 165, 37\u201348 (2014)","journal-title":"Discrete Appl. Math."},{"key":"1072_CR4","doi-asserted-by":"crossref","unstructured":"Asudeh, A., Jin, Z., Jagadish, H.V.: Assessing and remedying coverage for a given dataset. In: 35th Annual IEEE International Conference on Data Engineering, pp. 554\u2013565 (2019)","DOI":"10.1109\/ICDE.2019.00056"},{"issue":"1","key":"1072_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.4086\/toc.2011.v007a003","volume":"7","author":"P Austrin","year":"2011","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. Theory Comput. 7(1), 27\u201343 (2011)","journal-title":"Theory Comput."},{"key":"1072_CR6","unstructured":"Austrin, P., and Stankovic, A.: Global cardinality constraints make approximating some max-2-CSPs harder. In: Achlioptas, D., V\u00e9gh, L.A. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, vol. 145, pp. 24:1\u201324:17. Leibniz International Proceedings in Informatics (2019)"},{"key":"1072_CR7","doi-asserted-by":"crossref","unstructured":"Bansal, N.: Constructive algorithms for discrepancy minimization. In: 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 3\u201310 (2010)","DOI":"10.1109\/FOCS.2010.7"},{"issue":"1","key":"1072_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(81)90022-6","volume":"3","author":"J Beck","year":"1981","unstructured":"Beck, J., Fiala, T.: \u201cInteger-making\u2019\u2019 theorems. Discrete Appl. Math. 3(1), 1\u20138 (1981)","journal-title":"Discrete Appl. Math."},{"key":"1072_CR9","unstructured":"Bera, S., Chakrabarty, D., Flores, N., Negahbani, M.: Fair Algorithms for clustering. In: Wallach, H., Larochelle, H., Beygelzimer, A., d\u2019Alch\u00e9-Buc, F., Fox, E., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 32, pp. 4954\u20134965 (2019)"},{"key":"1072_CR10","first-page":"288","volume-title":"Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science","author":"T Carnes","year":"2008","unstructured":"Carnes, T., Shmoys, D.: Primal-dual schema for capacitated covering problems. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 5035, pp. 288\u2013302. Springer, Berlin (2008)"},{"key":"1072_CR11","unstructured":"Carr, R.D., Fleischer, L.K., V. Leung, J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 106\u2013115 (2000)"},{"key":"1072_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371","volume-title":"The Discrepancy Method: Randomness and Complexity","author":"B Chazelle","year":"2000","unstructured":"Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, Cambridge (2000)"},{"key":"1072_CR13","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 30, pp. 5029\u20135037 (2017)"},{"key":"1072_CR14","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0012-365X(01)00271-0","volume":"250","author":"B Doerr","year":"2002","unstructured":"Doerr, B.: Discrepancy in different numbers of colors. Discrete Math. 250, 63\u201370 (2002)","journal-title":"Discrete Math."},{"key":"1072_CR15","first-page":"39","volume-title":"Randomization, Approximation and Combinatorial Optimization, Lecture Notes in Computer Science","author":"B Doerr","year":"1999","unstructured":"Doerr, B., Srivastav, A.: Approximation of multi-color discrepancy. In: Hochbaum, D., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) Randomization, Approximation and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 1671, pp. 39\u201350. Springer, Berlin (1999)"},{"issue":"4","key":"1072_CR16","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"1072_CR17","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U Feige","year":"2001","unstructured":"Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41, 174\u2013211 (2001)","journal-title":"J. Algorithms"},{"issue":"1","key":"1072_CR18","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":"1072_CR19","volume-title":"Computers and Intractability\u2014A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability\u2014A Guide to the Theory of NP-Completeness. W. Freeman, H., & Co., San Francisco (1979)"},{"issue":"3","key":"1072_CR20","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00224-007-1309-3","volume":"41","author":"J Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41(3), 501\u2013520 (2007)","journal-title":"Theory Comput. Syst."},{"key":"1072_CR21","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: An FPT algorithm beating 2 approximation for k-cut. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2821\u20132837 (2018)","DOI":"10.1137\/1.9781611975031.179"},{"key":"1072_CR22","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: Faster exact and approximate algorithms for k-cut. In: 59th Annual IEEE Symposium on Foundations of Computer Science, pp. 113\u2013123 (2018)","DOI":"10.1109\/FOCS.2018.00020"},{"key":"1072_CR23","unstructured":"Guse, C.: Citi Bike neglects poor NYC neighborhoods and communities of color: report, New York Daily News, July 10, 2019. https:\/\/bit.ly\/3aEB4rz"},{"key":"1072_CR24","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/S0377-2217(02)00330-2","volume":"143","author":"Q Han","year":"2002","unstructured":"Han, Q., Ye, Y., Zhang, H., Zhang, J.: On approximation of max-vertex-cover. Eur. J. Oper. Res. 143, 342\u2013355 (2002)","journal-title":"Eur. J. Oper. Res."},{"key":"1072_CR25","unstructured":"Hardt, M., Price, E., Srebro, N.: Equality of opportunity in supervised learning. In: 30th International Conference on Neural Information Processing Systems, pp. 3323\u20133331 (2016)"},{"key":"1072_CR26","first-page":"94","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"DS Hochbaum","year":"1997","unstructured":"Hochbaum, D.S.: Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 94\u2013143. PWS Publishing Company, Boston (1997)"},{"key":"1072_CR27","unstructured":"Hunter, A.: Job ads show sexism still prevalent in most industries, HRD, February 22 (2019) (bit.ly\/38eom11)"},{"key":"1072_CR28","unstructured":"Ingold, D., Soper, S.: Amazon Doesn\u2019t Consider the Race of Its Customers. Should It?, Bloomberg, April 21 (2016)"},{"key":"1072_CR29","unstructured":"Jan, T.: Redlining was banned 50 years ago. It\u2019s still hurting minorities today, Washington Post, March 28 (2018)"},{"key":"1072_CR30","doi-asserted-by":"crossref","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 545\u2013554 (2009)","DOI":"10.1137\/1.9781611973068.60"},{"key":"1072_CR31","unstructured":"Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning, M. Sc. Thesis, Weizmann Institute of Science (1998)"},{"key":"1072_CR32","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. Cambridge University Press, Cambridge (2011)"},{"issue":"1","key":"1072_CR33","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1177\/0013124516630601","volume":"49","author":"J Lee","year":"2017","unstructured":"Lee, J., Lubienski, C.: The impact of school closures on equity of access in Chicago. Educ. Urban Soc. 49(1), 53\u201380 (2017)","journal-title":"Educ. Urban Soc."},{"key":"1072_CR34","first-page":"380","volume-title":"Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science","author":"A Levy","year":"2017","unstructured":"Levy, A., Ramadas, H., Rothvoss, T.: Deterministic discrepancy minimization via the multiplicative weight update method. In: Eisenbrand, F., Koenemann, J. (eds.) Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 10328, pp. 380\u2013391. Springer, Berlin (2017)"},{"key":"1072_CR35","unstructured":"Manurangsi, P.: A note on max k-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation. In: 2nd Symposium on Simplicity in Algorithms, pp. 15:1\u201315:21 (2019)"},{"issue":"1","key":"1072_CR36","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"key":"1072_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"1072_CR38","unstructured":"Mulshine, M.: A major flaw in Google\u2019s algorithm allegedly tagged two black people\u2019s faces with the word \u2019gorillas\u2019, Business Insider, July 1 (2015)"},{"key":"1072_CR39","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"N Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)"},{"key":"1072_CR40","doi-asserted-by":"publisher","first-page":"13","DOI":"10.3389\/fdata.2019.00013","volume":"2","author":"A Olteanu","year":"2019","unstructured":"Olteanu, A., Castillo, C., Diaz, F., Kiciman, E.: Social data: biases, methodological pitfalls, and ethical boundaries. Front. Big Data 2, 13 (2019)","journal-title":"Front. Big Data"},{"issue":"2","key":"1072_CR41","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A Panconesi","year":"1997","unstructured":"Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the Chernoff\u2013Hoeffding bounds. SIAM J. Comput. 26(2), 350\u2013368 (1997)","journal-title":"SIAM J. Comput."},{"key":"1072_CR42","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: gap location. Comput. Complex. 4, 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"key":"1072_CR43","unstructured":"Simon, M.: HP looking into claim webcams can\u2019t see black people, CNN, December 23 (2009)"},{"key":"1072_CR44","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1090\/S0002-9947-1985-0784009-0","volume":"289","author":"J Spencer","year":"1985","unstructured":"Spencer, J.: Six standard deviations suffice. Trans. Am. Math. Soc. 289, 679\u2013706 (1985)","journal-title":"Trans. Am. Math. Soc."},{"key":"1072_CR45","unstructured":"Spencer, S.: Amazon to Bring Same-Day Delivery to Roxbury After Outcry, Bloomberg, April 26 (2016)"},{"key":"1072_CR46","doi-asserted-by":"crossref","unstructured":"Srinivasan, A.: Distributions on level-sets with applications to approximation algorithms. In: 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 588\u2013597 (2001)","DOI":"10.1109\/SFCS.2001.959935"},{"key":"1072_CR47","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1017\/S0963548303005662","volume":"12","author":"A Srivastav","year":"2003","unstructured":"Srivastav, A.: Multicolour discrepancies. Comb. Probab. Comput. 12, 365\u2013399 (2003)","journal-title":"Comb. Probab. Comput."},{"key":"1072_CR48","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)"},{"issue":"4","key":"1072_CR49","first-page":"49","volume":"42","author":"A Yan","year":"2019","unstructured":"Yan, A., Howe, B.: Fairness in practice: a survey on equity in urban mobility. Data Eng. Bull. 42(4), 49 (2019)","journal-title":"Data Eng. Bull."},{"key":"1072_CR50","unstructured":"Zemel, R., Wu, Y., Swersky, K., Pitassi, T., Dwork, C.: Learning fair representations. In: 30th International Conference on Machine Learning, PMLR, vol. 28(3), pp. 325\u2013333 (2013)"},{"key":"1072_CR51","doi-asserted-by":"crossref","unstructured":"Zhang, B.H., Lemoine, B., Mitchell, M.: Mitigating unwanted biases with adversarial learning. In: AAAI\/ACM Conference on AI, Ethics, and Society, pp. 335\u2013340 (2018)","DOI":"10.1145\/3278721.3278779"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01072-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01072-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01072-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,25]],"date-time":"2023-04-25T00:03:15Z","timestamp":1682380995000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01072-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,7]]},"references-count":51,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1072"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01072-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,7]]},"assertion":[{"value":"17 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}