{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T19:30:51Z","timestamp":1718998251412},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T00:00:00Z","timestamp":1696636800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T00:00:00Z","timestamp":1696636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"JSPS KAKENHI","award":["20K04973 and 20H05964","20K04970"],"award-info":[{"award-number":["20K04973 and 20H05964","20K04970"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper. Res. Forum"],"DOI":"10.1007\/s43069-023-00260-1","type":"journal-article","created":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T07:01:32Z","timestamp":1696662092000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Monotone Diameter of Bisubmodular Polyhedra"],"prefix":"10.1007","volume":"4","author":[{"given":"Yasuko","family":"Matsui","sequence":"first","affiliation":[]},{"given":"Noriyoshi","family":"Sukegawa","sequence":"additional","affiliation":[]},{"given":"Ping","family":"Zhan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,7]]},"reference":[{"key":"260_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/BF02293053","volume":"8","author":"G Kalai","year":"1922","unstructured":"Kalai G (1922) Upper bounds for the diameter and height of graphs of convex polyhedra. Discrete Comput Geom 8:363\u2013372","journal-title":"Discrete Comput Geom"},{"key":"260_CR2","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1090\/S0273-0979-1992-00285-9","volume":"26","author":"G Kalai","year":"1992","unstructured":"Kalai G, Kleitman DJ (1992) A quasi-polynomial bound for the diameter of graphs of polyhedra. Bulletin of AMS 26:315\u2013316","journal-title":"Bulletin of AMS"},{"issue":"1","key":"260_CR3","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/PL00001277","volume":"4","author":"I Pak","year":"2000","unstructured":"Pak I (2000) Four questions on Birkhoff polytope. Annals of Combin 4(1):83\u201390","journal-title":"Annals of Combin"},{"issue":"2","key":"260_CR4","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1137\/0406019","volume":"6","author":"P Gritzmann","year":"1993","unstructured":"Gritzmann P, Sturmfels B (1993) Minkowski addition of polytopes: computation complexity and applications to Gr\u00f6bner bases. SIAM J Discrete Math 6(2):246\u2013269","journal-title":"SIAM J Discrete Math"},{"key":"260_CR5","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01589099","volume":"45","author":"D Naddef","year":"1998","unstructured":"Naddef D (1998) The Hirsch conjecture is true for (0,1)-polytopes. Math Program 45:109\u2013110","journal-title":"Math Program"},{"key":"260_CR6","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/140962310","volume":"28","author":"M Todd","year":"2014","unstructured":"Todd M (2014) An improved Kalai-Kleitman bound for the diameter of a polyhedron. SIAM J Discrete Math 28:1944\u20131947","journal-title":"SIAM J Discrete Math"},{"issue":"5","key":"260_CR7","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1007\/s11590-018-1276-4","volume":"12","author":"T Kuno","year":"2018","unstructured":"Kuno T, Sano Y, Tsuruda T (2018) Computing Kitahara-Mizuno\u2019s bound on the number of basic feasible solutions generated with the simplex algorithm. Optim Lett 12(5):933\u2013943","journal-title":"Optim Lett"},{"issue":"1","key":"260_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/10586458.2004.10504519","volume":"13","author":"J Pfeifle","year":"2004","unstructured":"Pfeifle J, Ziegler GM (2004) On the monotone upper bound problem. Experimental Math 13(1):1\u201311","journal-title":"Experimental Math"},{"key":"260_CR9","unstructured":"Kalai G (2017) 19 Polytope skeletons and paths. In: Handbook of Discrete and Computational Geometry 3rd edn by Csaba D. Toth, Joseph O\u2019Rourke, Jacob E. Goodman, Chapman and Hall, New York"},{"key":"260_CR10","volume-title":"Convex polytopes","author":"B Gr\u00fcnbaum","year":"2002","unstructured":"Gr\u00fcnbaum B (2002) Convex polytopes, 2nd edn. Springer","edition":"2"},{"issue":"4","key":"260_CR11","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1287\/moor.5.4.599","volume":"5","author":"M Todd","year":"1980","unstructured":"Todd M (1980) The monotonic bounded Hirsch conjecture is false for dimension at least 4. Math Oper Res 5(4):599\u2013601","journal-title":"Math Oper Res"},{"key":"260_CR12","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/s00454-018-0016-y","volume":"62","author":"N Sukegawa","year":"2019","unstructured":"Sukegawa N (2019) An asymptotically improved upper bound on the diameter of polyhedra. Discrete Comput Geom 62:690\u2013699","journal-title":"Discrete Comput Geom"},{"issue":"1\u20132","key":"260_CR13","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10107-017-1176-x","volume":"171","author":"S Borgwardt","year":"2018","unstructured":"Borgwardt S, De Loera JA, Finhold E (2018) The diameters of network-flow polytopes satisfy the Hirsch conjecture. Math Program 171(1\u20132):283\u2013309","journal-title":"Math Program"},{"key":"260_CR14","doi-asserted-by":"crossref","unstructured":"Sanit\u00e0 L (2018) The diameter of the fractional matching polytope and its hardness implications. IEEE 59th FOCS:910-921","DOI":"10.1109\/FOCS.2018.00090"},{"key":"260_CR15","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0167-6377(98)00011-X","volume":"22","author":"FJ Rispoli","year":"1998","unstructured":"Rispoli FJ (1998) The monotonic diameter of traveling salesman polytopes. Oper Res Lett 22:69\u201373","journal-title":"Oper Res Lett"},{"key":"260_CR16","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/S0895480196312462","volume":"11","author":"FJ Rispoli","year":"1998","unstructured":"Rispoli FJ, Cosares S (1998) A bound of 4 for the diameter of the symmetric traveling salesman polytope. SIAM J Discrete Math 11:373\u2013380","journal-title":"SIAM J Discrete Math"},{"key":"260_CR17","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BF01585502","volume":"7","author":"MW Padberg","year":"1974","unstructured":"Padberg MW, Rao MR (1974) The travelling salesman problem and a class of polyhedra of diameter two. Math Program 7:32\u201345","journal-title":"Math Program"},{"issue":"3","key":"260_CR18","doi-asserted-by":"publisher","first-page":"1746","DOI":"10.1137\/20M1315646","volume":"35","author":"M Blanchard","year":"2021","unstructured":"Blanchard M, De Loera JA, Louveaux Q (2021) On the length of monotone paths in polyhedra. SIAM J Discrete Math 35(3):1746\u20131768","journal-title":"SIAM J Discrete Math"},{"key":"260_CR19","doi-asserted-by":"crossref","unstructured":"Adler I, Papadimitriou C, Rubinstein A (2014) On simplex pivoting rules and complexity theory. IPCO\u201914:13-24","DOI":"10.1007\/978-3-319-07557-0_2"},{"key":"260_CR20","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/s10107-011-0482-y","volume":"137","author":"T Kitahara","year":"2013","unstructured":"Kitahara T, Mizuno S (2013) A bound for the number of different basic solutions generated by the simplex method. Math Program 137:579\u2013586","journal-title":"Math Program"},{"key":"260_CR21","first-page":"11","volume-title":"Michael J\u00fcnger","author":"J Edmonds","year":"2023","unstructured":"Edmonds J (2023) Submodular functions, matroids, and certain polyhedra. In: Reinelt Gerhard, Rinaldi Giovanni (eds) Michael J\u00fcnger. Springer, Combinatorial Optimization, pp 11\u201326"},{"key":"260_CR22","unstructured":"Fujishige S (2005) Submodular functions and optimization, vol 58, 2nd edn. Elsevier"},{"key":"260_CR23","doi-asserted-by":"crossref","unstructured":"Ward J, \u017divn\u00fd S (2014) Maximizing bisubmodular and k-submodular functions. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms:1468-1481","DOI":"10.1137\/1.9781611973402.108"},{"issue":"2\u20133","key":"260_CR24","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1080\/10556788.2020.1740219","volume":"36","author":"K Ando","year":"2021","unstructured":"Ando K, Fujishige S (2021) Signed ring families and signed posets. J Optim Methods Software 36(2\u20133):262\u2013278","journal-title":"J Optim Methods Software"},{"key":"260_CR25","unstructured":"Bilmes1 JA, Bai1 W (2017) Deep submodular functions. https:\/\/arxiv.org\/abs\/1701.08939"},{"key":"260_CR26","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF02592201","volume":"74","author":"K Ando","year":"1996","unstructured":"Ando K, Fujishige S (1996) On structures of bisubmodular polyhedra. Math Program 74:293\u2013317","journal-title":"Math Program"},{"key":"260_CR27","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/0097-3165(93)90052-A","volume":"62","author":"V Reiner","year":"1993","unstructured":"Reiner V (1993) Signed posets. J Combin Theory Ser A 62:324\u2013360","journal-title":"J Combin Theory Ser A"},{"key":"260_CR28","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.disopt.2014.02.002","volume":"12","author":"S Fujishige","year":"2014","unstructured":"Fujishige S (2014) Bisubmodular polyhedra, simplicial divisions, and discrete convexity. Discrete Optim 12:115\u2013120","journal-title":"Discrete Optim"},{"issue":"8","key":"260_CR29","doi-asserted-by":"publisher","first-page":"3507","DOI":"10.1090\/proc\/14977","volume":"148","author":"A Deza","year":"2020","unstructured":"Deza A, Pournin L, Sukegawa N (2020) The diameter of lattice zonotopes. Proc Am Math Soc 148(8):3507\u20133516","journal-title":"Proc Am Math Soc"},{"key":"260_CR30","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/BF01586058","volume":"54","author":"DM Topkis","year":"1992","unstructured":"Topkis DM (1992) Paths on polymatroids. Math. Program 54:335\u2013351","journal-title":"Program"},{"key":"260_CR31","doi-asserted-by":"crossref","unstructured":"Alexandrino AO, Miranda GHS, Lintzmayer CN, Dias1 Z (2021) Length-weighted $$\\lambda$$-rearrangement distance. J Combin Optim 41:579\u2013602","DOI":"10.1007\/s10878-020-00673-2"},{"key":"260_CR32","first-page":"90","volume":"48","author":"P Zhan","year":"2005","unstructured":"Zhan P (2005) Polyhedra and optimization related to a weak absolute majorization. J Oper Res Soc Japan 48:90\u201396","journal-title":"J Oper Res Soc Japan"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-023-00260-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-023-00260-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-023-00260-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,2]],"date-time":"2024-02-02T17:35:28Z","timestamp":1706895328000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-023-00260-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,7]]},"references-count":32,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["260"],"URL":"https:\/\/doi.org\/10.1007\/s43069-023-00260-1","relation":{},"ISSN":["2662-2556"],"issn-type":[{"value":"2662-2556","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,7]]},"assertion":[{"value":"5 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Ethics do not apply to this article as no ethic issue is included in this study.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics Approval"}},{"value":"It does not apply to this article since no participation was involved in this study.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to Participate"}},{"value":"The authors declares consent to publication.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}},{"value":"The authors declares no competing interests.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"76"}}