{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:33:06Z","timestamp":1742949186200,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030247652"},{"type":"electronic","value":"9783030247669"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-24766-9_31","type":"book-chapter","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T23:09:48Z","timestamp":1564528188000},"page":"423-437","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Balanced Stable Marriage: How Close Is Close Enough?"],"prefix":"10.1007","author":[{"given":"Sushmita","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjukta","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"31_CR1","unstructured":"Trends in Computational Social Choice. AI Access (2017)"},{"key":"31_CR2","unstructured":"Betzler, N.: A Multivariate Complexity Analysis of Voting Problems. Ph.D. thesis, Friedrich-Schiller-Universit\u00e4t Jena (2010)"},{"key":"31_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-642-30891-8_16","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"N Betzler","year":"2012","unstructured":"Betzler, N., Bredereck, R., Chen, J., Niedermeier, R.: Studies in computational aspects of voting. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 318\u2013363. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-30891-8_16"},{"key":"31_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107446984","volume-title":"Handbook of Computational Social Choice","author":"F Brandt","year":"2016","unstructured":"Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.: Handbook of Computational Social Choice. Cambridge University Press, London (2016)"},{"issue":"4","key":"31_CR5","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1109\/TST.2014.6867518","volume":"19","author":"R Bredereck","year":"2014","unstructured":"Bredereck, R., Chen, J., Faliszewski, P., Guo, J., Niedermeier, R., Woeginger, G.: Parameterized algorithmics for computational social choice: nine research challenges. Tsinghua Sci. Technol. 19(4), 358 (2014)","journal-title":"Tsinghua Sci. Technol."},{"key":"31_CR6","unstructured":"Chen, J., Hermelin, D., Sorge, M., Yedidsion, H.: How hard is it to satisfy (almost) all roommates. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 35:1\u201335:15 (2018)"},{"key":"31_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"1","key":"31_CR8","doi-asserted-by":"publisher","first-page":"3:1","DOI":"10.1145\/2462896.2462899","volume":"5","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. ACM Trans. Comput. Theory 5(1), 3:1\u20133:11 (2013)","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1&2","key":"31_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theor. Comput. Sci. 141(1&2), 109\u2013131 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"31_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"1516","DOI":"10.1007\/978-1-4939-2864-4_785","volume-title":"Encyclopedia of Algorithms","author":"Piotr Faliszewski","year":"2016","unstructured":"Faliszewski, P., Niedermeier, R.: Parameterization in computational social choice. In: Encyclopedia of Algorithms, pp. 1516\u20131520 (2016)"},{"key":"31_CR12","unstructured":"Feder, T.: Stable networks and product graphs. Ph.D. thesis, Stanford University (1990)"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Monthly 69, 9\u201315 (1962)","journal-title":"Am. Math. Monthly"},{"issue":"4","key":"31_CR14","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0166-218X(85)90074-5","volume":"11","author":"D Gale","year":"1985","unstructured":"Gale, D., Sotomayor, M.: Some remarks on the stable matching problem. Discrete Appl. Math. 11(4), 223\u2013232 (1985)","journal-title":"Discrete Appl. Math."},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"Garg, S., Philip, G.: Raising the bar for vertex cover: Fixed-parameter tractability above a higher guarantee. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1152\u20131166 (2016)","DOI":"10.1137\/1.9781611974331.ch80"},{"key":"31_CR16","unstructured":"Gupta, S., Roy, S., Saurabh, S., Zehavi, M.: Balanced stable marriage: how close is close enough? CoRR abs\/1707.09545 (2017)"},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-319-66700-3_9","volume-title":"Algorithmic Game Theory","author":"Sushmita Gupta","year":"2017","unstructured":"Gupta, S., Roy, S., Saurabh, S., Zehavi, M.: Group activity selection on graphs: Parameterized analysis. In: Proceedings of 10th International Symposium Algorithmic Game Theory (SAGT), pp. 106\u2013118 (2017)"},{"key":"31_CR18","unstructured":"Gupta, S., Saurabh, S., Zehavi, M.: On treewidth and stable marriage. CoRR abs\/1707.05404 (2017)"},{"issue":"1","key":"31_CR19","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0216010","volume":"16","author":"D Gusfield","year":"1987","unstructured":"Gusfield, D.: Three fast algorithms for four problems in stable marriage. SIAM J. Comput. 16(1), 111\u2013128 (1987)","journal-title":"SIAM J. Comput."},{"key":"31_CR20","unstructured":"Gusfield, D., Irving, R.W.: The Stable Marriage Problem - Structure and Algorithms. Foundations of Computing Series. MIT Press (1989)"},{"key":"31_CR21","unstructured":"Igarashi, A., Bredereck, R., Elkind, E.: On parameterized complexity of group activity selection problems on social networks. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp. 1575\u20131577 (2017)"},{"key":"31_CR22","doi-asserted-by":"crossref","unstructured":"Igarashi, A., Peters, D., Elkind, E.: Group activity selection on social networks. In: Proceedings of the 31st Conference on Artificial Intelligence (AAAI), pp. 565\u2013571 (2017)","DOI":"10.1609\/aaai.v31i1.10617"},{"key":"31_CR23","doi-asserted-by":"crossref","unstructured":"Knuth, D.E.: Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms. CRM Proceedings & Lecture notes, American Mathematical Society (1997)","DOI":"10.1090\/crmp\/010"},{"key":"31_CR24","doi-asserted-by":"crossref","unstructured":"Lee, H., Williams, V.: Complexity of the stable invitations problem. In: Proceedings of the 31st Conference on Artificial Intelligence (AAAI), pp. 579\u2013585 (2017)","DOI":"10.1609\/aaai.v31i1.10562"},{"key":"31_CR25","unstructured":"Lee, H., Williams, V.: Parameterized complexity of group activity selection. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp. 353\u2013361 (2017)"},{"issue":"2","key":"31_CR26","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/2566616","volume":"11","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2), 15:1\u201315:31 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"31_CR27","doi-asserted-by":"crossref","unstructured":"Manlove, D.F.: Algorithmics of Matching Under Preferences, Series on Theoretical Computer Science, vol. 2. WorldScientific (2013)","DOI":"10.1142\/8591"},{"issue":"1","key":"31_CR28","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/s00453-009-9326-z","volume":"58","author":"D Marx","year":"2010","unstructured":"Marx, D., Schlotter, I.: Parameterized complexity and local search approaches for the stable marriage problem with ties. Algorithmica 58(1), 170\u2013187 (2010)","journal-title":"Algorithmica"},{"issue":"1","key":"31_CR29","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.disopt.2010.07.004","volume":"8","author":"D Marx","year":"2011","unstructured":"Marx, D., Schlotter, I.: Stable assignment with couples: parameterized complexity and local search. Discrete Optim. 8(1), 25\u201340 (2011)","journal-title":"Discrete Optim."},{"key":"31_CR30","unstructured":"Meeks, K., Rastegari, B.: Solving hard stable matching problems involving groups of similar agents. CoRR abs\/1708.04109 (2017)"},{"key":"31_CR31","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-319-66700-3_25","volume-title":"Algorithmic Game Theory","author":"Matthias Mnich","year":"2017","unstructured":"Mnich, M., Schlotter, I.: Stable marriage with covering constraints-a complete computational trichotomy. In: Proceedings of the 10th International Symposium of Algorithmic Game Theory (SAGT), pp. 320\u2013332 (2017)"},{"key":"31_CR32","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-642-23719-5_33","volume-title":"Algorithms \u2013 ESA 2011","author":"Venkatesh Raman","year":"2011","unstructured":"Raman, V., Ramanujan, M.S., Saurabh, S.: Paths, flowers and vertex cover. In: Proceedings of the 19th Annual European Symposium on Algorithms (ESA), pp. 382\u2013393 (2011)"}],"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-030-24766-9_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:55:27Z","timestamp":1710266127000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-24766-9_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030247652","9783030247669"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24766-9_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 July 2019","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":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edmonton, AB","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":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}