{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T21:11:15Z","timestamp":1771535475714,"version":"3.50.1"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031327254","type":"print"},{"value":"9783031327261","type":"electronic"}],"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-32726-1_6","type":"book-chapter","created":{"date-parts":[[2023,5,21]],"date-time":"2023-05-21T20:28:43Z","timestamp":1684700923000},"page":"72-86","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Inapproximability of\u00a0Shortest Paths on\u00a0Perfect Matching Polytopes"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2312-0967","authenticated-orcid":false,"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4234-6136","authenticated-orcid":false,"given":"Raphael","family":"Steiner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,22]]},"reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-319-07557-0_2","volume-title":"Integer Programming and Combinatorial Optimization","author":"I Adler","year":"2014","unstructured":"Adler, I., Papadimitriou, C., Rubinstein, A.: On simplex pivoting rules and complexity theory. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 13\u201324. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07557-0_2"},{"issue":"1","key":"6_CR2","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/s00453-020-00751-1","volume":"83","author":"O Aichholzer","year":"2021","unstructured":"Aichholzer, O., et al.: Flip distances between graph orientations. Algorithmica 83(1), 116\u2013143 (2021)","journal-title":"Algorithmica"},{"issue":"4","key":"6_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"6_CR4","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10107-016-1008-4","volume":"161","author":"D Avis","year":"2017","unstructured":"Avis, D., Friedmann, O.: An exponential lower bound for Cunningham\u2019s rule. Math. Program. 161(1\u20132), 271\u2013305 (2017)","journal-title":"Math. Program."},{"issue":"3","key":"6_CR5","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1137\/0218039","volume":"18","author":"F Barahona","year":"1989","unstructured":"Barahona, F., Tardos, \u00c9.: Note on Weintraub\u2019s minimum-cost circulation algorithm. SIAM J. Comput. 18(3), 579\u2013583 (1989)","journal-title":"SIAM J. Comput."},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-540-27836-8_21","volume-title":"Automata, Languages and Programming","author":"A Bj\u00f6rklund","year":"2004","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Khanna, S.: Approximating longest directed paths and cycles. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 222\u2013233. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27836-8_21"},{"issue":"2","key":"6_CR7","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1287\/moor.2.2.103","volume":"2","author":"RG Bland","year":"1977","unstructured":"Bland, R.G.: New finite pivoting rules for the simplex method. Math. Oper. Res. 2(2), 103\u2013107 (1977)","journal-title":"Math. Oper. Res."},{"key":"6_CR8","unstructured":"Bonamy, M., et al.: The perfect matching reconfiguration problem. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26\u201330, 2019, Aachen, Germany. LIPIcs, vol. 138, pp. 80:1\u201380:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"issue":"3","key":"6_CR9","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.orl.2021.02.003","volume":"49","author":"S Borgwardt","year":"2021","unstructured":"Borgwardt, S., Brand, C., Feldmann, A.E., Kouteck\u00fd, M.: A note on the approximability of deepest-descent circuit steps. Oper. Res. Lett. 49(3), 310\u2013315 (2021)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"6_CR10","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1137\/140976868","volume":"29","author":"S Borgwardt","year":"2015","unstructured":"Borgwardt, S., Finhold, E., Hemmecke, R.: On the circuit diameter of dual transportation polyhedra. SIAM J. Discrete Math. 29(1), 113\u2013121 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.dam.2019.07.025","volume":"308","author":"S Borgwardt","year":"2022","unstructured":"Borgwardt, S., Viss, C.: A polyhedral model for enumeration and optimization over the set of circuits. Discret. Appl. Math. 308, 68\u201383 (2022)","journal-title":"Discret. Appl. Math."},{"key":"6_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-030-30786-8_13","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"N Bousquet","year":"2019","unstructured":"Bousquet, N., Hatanaka, T., Ito, T., M\u00fchlenthaler, M.: Shortest reconfiguration of matchings. In: Sau, I., Thilikos, D.M. (eds.) WG 2019. LNCS, vol. 11789, pp. 162\u2013174. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-30786-8_13"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V.: On certain polytopes associated with graphs. J. Comb. Theory, Ser. B 18(2), 138\u2013154 (1975)","DOI":"10.1016\/0095-8956(75)90041-6"},{"key":"6_CR14","first-page":"480","volume":"81","author":"SM Cioab\u0103","year":"2021","unstructured":"Cioab\u0103, S.M., Royle, G., Tan, Z.K.: On the flip graphs on perfect matchings of complete graphs and signed reversal graphs. Australas. J. Comb. 81, 480\u2013497 (2021)","journal-title":"Australas. J. Comb."},{"issue":"4","key":"6_CR15","doi-asserted-by":"publisher","first-page":"2494","DOI":"10.1137\/151002915","volume":"25","author":"JA De Loera","year":"2015","unstructured":"De Loera, J.A., Hemmecke, R., Lee, J.: On augmentation algorithms for linear and integer-linear programming: from Edmonds-Karp to Bland and beyond. SIAM J. Optim. 25(4), 2494\u20132511 (2015)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"6_CR16","doi-asserted-by":"publisher","first-page":"2156","DOI":"10.1137\/21M1419994","volume":"32","author":"JA De Loera","year":"2022","unstructured":"De Loera, J.A., Kafer, S., Sanit\u00e0, L.: Pivot rules for circuit-augmentation algorithms in linear optimization. SIAM J. Optim. 32(3), 2156\u20132179 (2022)","journal-title":"SIAM J. Optim."},{"issue":"25","key":"6_CR17","doi-asserted-by":"publisher","first-page":"14600","DOI":"10.1073\/pnas.95.25.14600","volume":"95","author":"PW Diaconis","year":"1998","unstructured":"Diaconis, P.W., Holmes, S.P.: Matchings and phylogenetic trees. Proc. Natl. Acad. Sci. USA 95(25), 14600\u201314602 (1998)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"6","key":"6_CR18","first-page":"1","volume":"7","author":"PW Diaconis","year":"2002","unstructured":"Diaconis, P.W., Holmes, S.P.: Random walks on trees and matchings. Electron. J. Probab. 7(6), 1\u201317 (2002)","journal-title":"Electron. J. Probab."},{"key":"6_CR19","unstructured":"Disser, Y., Friedmann, O., Hopp, A.V.: An exponential lower bound for Zadeh\u2019s pivot rule. CoRR abs\/1911.01074 (2019). http:\/\/arxiv.org\/abs\/1911.01074"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Disser, Y., Skutella, M.: The simplex algorithm is NP-mighty. ACM Trans. Algorithms 15(1), 5:1\u20135:19 (2019)","DOI":"10.1145\/3280847"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Savani, R.: The complexity of the simplex method. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14\u201317, 2015, pp. 201\u2013208. ACM (2015)","DOI":"10.1145\/2746539.2746558"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Nie, S.: Finding a long directed cycle. ACM Trans. Algorithms 4(1), 7:1\u20137:21 (2008)","DOI":"10.1145\/1328911.1328918"},{"key":"6_CR23","unstructured":"Gima, T., Ito, T., Kobayashi, Y., Otachi, Y.: Algorithmic meta-theorems for combinatorial reconfiguration revisited. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algorithms, ESA 2022, September 5\u20139, 2022, Berlin\/Potsdam, Germany. LIPIcs, vol. 244, pp. 61:1\u201361:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"4","key":"6_CR24","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0166-218X(79)90004-0","volume":"1","author":"D Goldfarb","year":"1979","unstructured":"Goldfarb, D., Sit, W.Y.: Worst case behavior of the steepest edge simplex method. Discret. Appl. Math. 1(4), 277\u2013285 (1979)","journal-title":"Discret. Appl. Math."},{"key":"6_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-030-10801-4_18","volume-title":"SOFSEM 2019: Theory and Practice of Computer Science","author":"M Gupta","year":"2019","unstructured":"Gupta, M., Kumar, H., Misra, N.: On the complexity of optimal matching reconfiguration. In: Catania, B., Kr\u00e1lovi\u010d, R., Nawrocki, J., Pighizzini, G. (eds.) SOFSEM 2019. LNCS, vol. 11376, pp. 221\u2013233. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-10801-4_18"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Hansen, T.D., Zwick, U.: An improved version of the random-facet pivoting rule for the simplex algorithm. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14\u201317, 2015, pp. 209\u2013218. ACM (2015)","DOI":"10.1145\/2746539.2746557"},{"key":"6_CR27","unstructured":"van den Heuvel, J.: The complexity of change. In: Blackburn, S.R., Gerke, S., Wildon, M. (eds.) Surveys in Combinatorics 2013, London Mathematical Society Lecture Note Series, vol. 409, pp. 127\u2013160. Cambridge University Press (2013)"},{"issue":"12\u201314","key":"6_CR28","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T., et al.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"6_CR29","doi-asserted-by":"publisher","first-page":"1102","DOI":"10.1137\/20M1364370","volume":"36","author":"T Ito","year":"2022","unstructured":"Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y., Okamoto, Y.: Shortest reconfiguration of perfect matchings via alternating cycles. SIAM J. Discret. Math. 36(2), 1102\u20131123 (2022)","journal-title":"SIAM J. Discret. Math."},{"issue":"1\u20133","key":"6_CR30","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0012-365X(01)00167-4","volume":"242","author":"S Iwata","year":"2002","unstructured":"Iwata, S.: On matroid intersection adjacency. Discret. Math. 242(1\u20133), 277\u2013281 (2002)","journal-title":"Discret. Math."},{"issue":"4","key":"6_CR31","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0012-365X(73)90171-4","volume":"4","author":"RG Jeroslow","year":"1973","unstructured":"Jeroslow, R.G.: The simplex algorithm with the pivot rule of maximizing criterion improvement. Discret. Math. 4(4), 367\u2013377 (1973)","journal-title":"Discret. Math."},{"issue":"1","key":"6_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/17M1152115","volume":"33","author":"S Kafer","year":"2019","unstructured":"Kafer, S., Pashkovich, K., Sanit\u00e0, L.: On the circuit diameter of some combinatorial polytopes. SIAM J. Discret. Math. 33(1), 1\u201325 (2019)","journal-title":"SIAM J. Discret. Math."},{"key":"6_CR33","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.tcs.2012.03.004","volume":"439","author":"M Kaminski","year":"2012","unstructured":"Kaminski, M., Medvedev, P., Milanic, M.: Complexity of independent set reconfigurability problems. Theor. Comput. Sci. 439, 9\u201315 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"#cr-split#-6_CR34.1","unstructured":"Klee, V., Minty, G.J.: How good is the simplex algorithm? In: Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969"},{"key":"#cr-split#-6_CR34.2","unstructured":"dedicated to the memory of Theodore S. Motzkin), pp. 159-175. Academic Press, New York (1972)"},{"issue":"2","key":"6_CR35","first-page":"47","volume":"11","author":"RF Monroy","year":"2009","unstructured":"Monroy, R.F., Flores-Pe\u00f1aloza, D., Huemer, C., Hurtado, F., Wood, D.R., Urrutia, J.: On the chromatic number of some flip graphs. Discret. Math. Theor. Comput. Sci. 11(2), 47\u201356 (2009)","journal-title":"Discret. Math. Theor. Comput. Sci."},{"issue":"4","key":"6_CR36","doi-asserted-by":"publisher","first-page":"52","DOI":"10.3390\/a11040052","volume":"11","author":"N Nishimura","year":"2018","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52 (2018)","journal-title":"Algorithms"},{"issue":"1","key":"6_CR37","doi-asserted-by":"publisher","first-page":"383","DOI":"10.4007\/annals.2012.176.1.7","volume":"176","author":"F Santos","year":"2012","unstructured":"Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176(1), 383\u2013412 (2012)","journal-title":"Ann. Math."},{"key":"6_CR38","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24. Springer (2003)"},{"key":"6_CR39","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the International Congress of Mathematicians (ICM 2018), pp. 3447\u20133487. World Scientific (2018)","DOI":"10.1142\/9789813272880_0188"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-32726-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,21]],"date-time":"2023-05-21T20:29:31Z","timestamp":1684700971000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-32726-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031327254","9783031327261"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-32726-1_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"22 May 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Madison, WI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","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":"21 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/optimization.discovery.wisc.edu\/ipco-2023-madison\/","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":"119","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":"33","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":"28% - 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":"2","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)"}}]}}