{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T11:53:42Z","timestamp":1743076422392,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030927011"},{"type":"electronic","value":"9783030927028"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-92702-8_4","type":"book-chapter","created":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T06:00:24Z","timestamp":1641016824000},"page":"48-64","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tight Inapproximability of\u00a0Minimum Maximal Matching on\u00a0Bipartite Graphs and\u00a0Related Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4926-8353","authenticated-orcid":false,"given":"Szymon","family":"Dudycz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1052-2801","authenticated-orcid":false,"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6517-0014","authenticated-orcid":false,"given":"Jan","family":"Marcinkowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,1]]},"reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-642-32512-0_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"P Austrin","year":"2012","unstructured":"Austrin, P., Pitassi, T., Wu, Yu.: Inapproximability of treewidth, one-shot pebbling, and related layout problems. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM -2012. LNCS, vol. 7408, pp. 13\u201324. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32512-0_2"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khot, S.: Optimal long code test with one free bit. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, Atlanta, Georgia, USA, 25\u201327 October 2009, pp. 453\u2013462. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.23"},{"key":"4_CR3","unstructured":"Bhangale, A., Gandhi, R., Hajiaghayi, M.T., Khandekar, R., Kortsarz, G.: Bicovering: covering edges with two small subsets of vertices. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, 11\u201315 July 2016, vol. 55 of LIPIcs, pp. 6:1\u20136:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/3-540-45253-2_13","volume-title":"Algorithms - ESA 2000","author":"RD Carr","year":"2000","unstructured":"Carr, R.D., Fujito, T., Konjevod, G., Parekh, O.: A 2 1\/10-approximation algorithm for a generalization of the weighted edge-dominating set problem. In: Paterson, M.S. (ed.) ESA 2000. LNCS, vol. 1879, pp. 132\u2013142. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-45253-2_13"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chatziafratis, V.: Approximate hierarchical clustering via sparsest cut and spreading metrics. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, 16\u201319 January 2017, pp. 841\u2013854. SIAM (2017)","DOI":"10.1137\/1.9781611974782.53"},{"issue":"3","key":"4_CR6","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10878-006-7908-0","volume":"11","author":"M Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of edge dominating set problems. J. Comb. Optim. 11(3), 279\u2013290 (2006)","journal-title":"J. Comb. Optim."},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Dinur, I., Khot, S., Kindler, G., Minzer, D., Safra, M.: On non-optimally expanding sets in grassmann graphs. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, 25\u201329 June 2018, pp. 940\u2013951. ACM (2018)","DOI":"10.1145\/3188745.3188806"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Dinur, I., Khot, S., Kindler, G., Minzer, D., Safra, M.: Towards a proof of the 2-to-1 games conjecture? In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, 25\u201329 June 2018, pp. 376\u2013389. ACM (2018)","DOI":"10.1145\/3188745.3188804"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-030-17953-3_14","volume-title":"Integer Programming and Combinatorial Optimization","author":"S Dudycz","year":"2019","unstructured":"Dudycz, S., Lewandowski, M., Marcinkowski, J.: Tight approximation ratio for minimum maximal matching. In: Lodi, A., Nagarajan, V. (eds.) IPCO 2019. LNCS, vol. 11480, pp. 181\u2013193. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17953-3_14"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-33293-7_5","volume-title":"Parameterized and Exact Computation","author":"B Escoffier","year":"2012","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T., Xiao, M.: New results on polynomial inapproximability and fixed parameter approximability of edge dominating set. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 25\u201336. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33293-7_5"},{"issue":"3","key":"4_CR11","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0166-218X(00)00383-8","volume":"118","author":"T Fujito","year":"2002","unstructured":"Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight edge dominating set problem. Disc. Appl. Math. 118(3), 199\u2013207 (2002)","journal-title":"Disc. Appl. Math."},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-540-93980-1_21","volume-title":"Approximation and Online Algorithms","author":"Z Gotthilf","year":"2009","unstructured":"Gotthilf, Z., Lewenstein, M., Rainshmidt, E.: A $$(2 - c \\frac{\\log {n}}{n})$$ approximation algorithm for the minimum maximal matching problem. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol. 5426, pp. 267\u2013278. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-540-93980-1_21"},{"key":"4_CR13","unstructured":"Hardt, M., Moitra, A.: Algorithms and hardness for robust subspace recovery. In: Shalev-Shwartz, S., Steinwart, I. (eds.) COLT 2013 - The 26th Annual Conference on Learning Theory, Princeton University, NJ, USA, 12\u201314 June 2013, vol. 30 of JMLR Workshop and Conference Proceedings, pp. 354\u2013375. JMLR.org (2013)"},{"key":"4_CR14","unstructured":"Huang, C.-C., Iwama, K., Miyazaki, S., Yanagisawa, H.: A tight approximation bound for the stable marriage problem with restricted ties. In: Garg, N., Jansen, K., Rao, A., Rolim, J.D.M. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2015, Princeton, NJ, USA, 24\u201326 August 2015, vol. 40 of LIPIcs, pp. 361\u2013380. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015)"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Reif, J.H. (ed.) Proceedings on 34th Annual ACM Symposium on Theory of Computing, Montr\u00e9al, Qu\u00e9bec, Canada, 19\u201321 May 2002, pp. 767\u2013775. ACM (2002)","DOI":"10.1145\/509907.510017"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Khot, S., Minzer, D., Safra, M.: Pseudorandom sets in grassmann graph have near-perfect expansion. In: Thorup, M. (ed.) 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 7\u20139 October 2018, pp. 592\u2013601. IEEE Computer Society (2018)","DOI":"10.1109\/FOCS.2018.00062"},{"issue":"3","key":"4_CR17","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\\epsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Khot, S., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into $$\\ell _1$$. J. ACM 62(1), 8:1\u20138:39 (2015)","DOI":"10.1145\/2629614"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Louis, A., Raghavendra, P., Vempala, S.S.: The complexity of approximating vertex expansion. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, USA, 26\u201329 October 2013, pp. 360\u2013369. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.46"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Inapproximability of maximum edge biclique, maximum balanced biclique and minimum k-cut from the small set expansion hypothesis. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland, 10\u201314 July 2017, pp. 79:1\u201379:14 (2017)","DOI":"10.3390\/a11010010"},{"key":"4_CR21","unstructured":"Parekh, O.: Edge dominating and hypomatchable sets. In: Eppstein, D. (ed.) Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, 6\u20138 January 2002, pp. 287\u2013291. ACM\/SIAM (2002)"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Schulman, L.J. (ed.) Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010, pp. 755\u2013764. ACM (2010)","DOI":"10.1145\/1806689.1806792"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions between expansion problems. In: Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, 26\u201329 June 2012, pp. 64\u201373 (2012)","DOI":"10.1109\/CCC.2012.43"},{"issue":"1","key":"4_CR24","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2011.10.001","volume":"414","author":"R Schmied","year":"2012","unstructured":"Schmied, R., Viehmann, C.: Approximating edge dominating set in dense graphs. Theor. Comput. Sci. 414(1), 92\u201399 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"4_CR25","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-92702-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:10:28Z","timestamp":1726409428000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-92702-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030927011","9783030927028"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-92702-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"1 January 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lisbon","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Portugal","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/algo2021.tecnico.ulisboa.pt\/WAOA2021\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-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":"31","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":"16","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":"52% - 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","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}