{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:46:59Z","timestamp":1742957219679,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031389054"},{"type":"electronic","value":"9783031389061"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-38906-1_6","type":"book-chapter","created":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T16:05:14Z","timestamp":1690473914000},"page":"79-92","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Socially Fair Matching: Exact and\u00a0Approximation Algorithms"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8875-0102","authenticated-orcid":false,"given":"Sayan","family":"Bandyapadhyay","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":false,"given":"Fedor","family":"Fomin","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0184-5932","authenticated-orcid":false,"given":"Tanmay","family":"Inamdar","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6213-8687","authenticated-orcid":false,"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9436-7310","authenticated-orcid":false,"given":"Kirill","family":"Simonov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,28]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Abbasi, M., Bhaskara, A., Venkatasubramanian, S.: Fair clustering via equitable group representations. In: Elish, M.C., Isaac, W., Zemel, R.S. (eds.) FAccT 2021: 2021 ACM Conference on Fairness, Accountability, and Transparency, Virtual Event\/Toronto, Canada, 3\u201310 March 2021, pp. 504\u2013514. ACM (2021)","DOI":"10.1145\/3442188.3445913"},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.dam.2015.01.008","volume":"196","author":"M Barketau","year":"2015","unstructured":"Barketau, M., Pesch, E., Shafransky, Y.: Minimizing maximum weight of subsets of a maximum matching in a bipartite graph. Discrete Appl. Math. 196, 4\u201319 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"6_CR3","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s10107-009-0307-4","volume":"128","author":"A Berger","year":"2011","unstructured":"Berger, A., Bonifaci, V., Grandoni, F., Sch\u00e4fer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Math. Program. 128(1\u20132), 355\u2013372 (2011). https:\/\/doi.org\/10.1007\/s10107-009-0307-4","journal-title":"Math. Program."},{"issue":"2","key":"6_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1089\/big.2016.0047","volume":"5","author":"A Chouldechova","year":"2017","unstructured":"Chouldechova, A.: Fair prediction with disparate impact: a study of bias in recidivism prediction instruments. Big Data 5(2), 153\u2013163 (2017)","journal-title":"Big Data"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Corbett-Davies, S., Pierson, E., Feller, A., Goel, S., Huq, A.: Algorithmic decision making and the cost of fairness. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, 13\u201317 August 2017, pp. 797\u2013806. ACM (2017)","DOI":"10.1145\/3097983.3098095"},{"issue":"3","key":"6_CR6","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1134\/S1990478921030042","volume":"15","author":"O Duginov","year":"2021","unstructured":"Duginov, O.: Weighted perfect matching with constraints on the total weight of its parts. J. Appl. Ind. Math. 15(3), 393\u2013412 (2021)","journal-title":"J. Appl. Ind. Math."},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Dwork, C., Hardt, M., Pitassi, T., Reingold, O., Zemel, R.: Fairness through awareness. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 214\u2013226 (2012)","DOI":"10.1145\/2090236.2090255"},{"key":"6_CR8","unstructured":"Dwork, C., Ilvento, C.: Group fairness under composition. In: Proceedings of the 2018 Conference on Fairness, Accountability, and Transparency (FAT* 2018) (2018)"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Feldman, M., Friedler, S.A., Moeller, J., Scheidegger, C., Venkatasubramanian, S.: Certifying and removing disparate impact. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 259\u2013268 (2015)","DOI":"10.1145\/2783258.2783311"},{"issue":"5","key":"6_CR11","doi-asserted-by":"publisher","first-page":"1291","DOI":"10.1007\/s10618-020-00675-y","volume":"34","author":"D Garc\u00eda-Soriano","year":"2020","unstructured":"Garc\u00eda-Soriano, D., Bonchi, F.: Fair-by-design matching. Data Min. Knowl. Disc. 34(5), 1291\u20131335 (2020). https:\/\/doi.org\/10.1007\/s10618-020-00675-y","journal-title":"Data Min. Knowl. Disc."},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Ghadiri, M., Samadi, S., Vempala, S.S.: Socially fair k-means clustering. In: Elish, M.C., Isaac, W., Zemel, R.S. (eds.) FAccT 2021: 2021 ACM Conference on Fairness, Accountability, and Transparency, Virtual Event\/Toronto, Canada, 3\u201310 March 2021, pp. 438\u2013448. ACM (2021)","DOI":"10.1145\/3442188.3445906"},{"issue":"3","key":"6_CR13","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1007\/s00453-015-9994-9","volume":"74","author":"C Huang","year":"2016","unstructured":"Huang, C., Kavitha, T., Mehlhorn, K., Michail, D.: Fair matchings and related problems. Algorithmica 74(3), 1184\u20131203 (2016)","journal-title":"Algorithmica"},{"key":"6_CR14","unstructured":"Kamada, Y., Kojima, F.: Fair matching under constraints: Theory and applications (2020)"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Kamishima, T., Akaho, S., Sakuma, J.: Fairness-aware learning through regularization approach. In: Spiliopoulou, M., et al. (eds.) Data Mining Workshops (ICDMW), 2011 IEEE 11th International Conference on, Vancouver, BC, Canada, 11 December 2011, pp. 643\u2013650. IEEE Computer Society (2011)","DOI":"10.1109\/ICDMW.2011.83"},{"key":"6_CR16","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"issue":"2","key":"6_CR17","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. Theory 27(2), 431\u2013447 (2006)","journal-title":"Econ. Theory"},{"key":"6_CR18","unstructured":"Kleinberg, J., Mullainathan, S., Raghavan, M.: Inherent trade-offs in the fair determination of risk scores. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"3","key":"6_CR19","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1016\/j.ejor.2015.06.041","volume":"247","author":"D Kress","year":"2015","unstructured":"Kress, D., Meiswinkel, S., Pesch, E.: The partitioning min-max weighted matching problem. Eur. J. Oper. Res. 247(3), 745\u2013754 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"6_CR20","unstructured":"Makarychev, Y., Vakilian, A.: Approximation algorithms for socially fair clustering. CoRR abs\/2103.02512 (2021)"},{"key":"6_CR21","doi-asserted-by":"publisher","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12\u201314 November 2000, Redondo Beach, California, USA, pp. 86\u201392. IEEE Computer Society (2000). https:\/\/doi.org\/10.1109\/SFCS.2000.892068","DOI":"10.1109\/SFCS.2000.892068"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Thanh, B.L., Ruggieri, S., Turini, F.: k-NN as an implementation of situation testing for discrimination discovery and prevention. In: Apt\u00e9, C., Ghosh, J., Smyth, P. (eds.) Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, 21\u201324 August 2011, pp. 502\u2013510. ACM (2011)","DOI":"10.1145\/2020408.2020488"},{"key":"6_CR23","unstructured":"Wikipedia contributors: Sister city \u2014 Wikipedia, the free encyclopedia (2022). https:\/\/en.wikipedia.org\/w\/index.php?title=Sister_city&oldid=1107517947. Accessed 25 Sept 2022"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-38906-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T05:03:01Z","timestamp":1729832581000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-38906-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031389054","9783031389061"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-38906-1_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"28 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Algorithms and Data Structures Symposium","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Montreal, QC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}