{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:20:01Z","timestamp":1767140401768,"version":"build-2238731810"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T00:00:00Z","timestamp":1591228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T00:00:00Z","timestamp":1591228800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In this paper we present a scaling algorithm for minimizing arbitrary functions over vertices of polytopes in an oracle model of computation which includes an augmentation oracle. For the binary case, when the vertices are 0\u20131 vectors, we show that the oracle time is polynomial. Also, this algorithm allows us to generalize some concepts of combinatorial optimization concerning performance bounds of greedy algorithms and leads to new bounds for the complexity of the simplex method.<\/jats:p>","DOI":"10.1007\/s10107-020-01522-0","type":"journal-article","created":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T11:03:21Z","timestamp":1591268601000},"page":"89-102","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A scaling algorithm for optimizing arbitrary functions over vertices of polytopes"],"prefix":"10.1007","volume":"190","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3164-3415","authenticated-orcid":false,"given":"Sergei","family":"Chubanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,4]]},"reference":[{"key":"1522_CR1","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/s00454-014-9601-x","volume":"52","author":"N Bonifas","year":"2014","unstructured":"Bonifas, N., Di Summa, M., Eisenbrand, F., H\u00e4hnle, N., Niemeier, M.: On sub-determinants and the diameter of polyhedra. Discrete Comput. Geom. 52, 102\u2013115 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"1522_CR2","unstructured":"Chubanov, S.: A generalized simplex method for integer problems given by verification oracles. Optimization Online (2016)"},{"key":"1522_CR3","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\u2013Karp to Bland and beyond. SIAM J. Optim. 25, 2494\u20132511 (2015)","journal-title":"SIAM J. Optim."},{"key":"1522_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01582563","volume":"64","author":"M Dyer","year":"1994","unstructured":"Dyer, M., Frieze, A.: Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Program. 64, 1\u201316 (1994)","journal-title":"Math. Program."},{"key":"1522_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 49\u201365 (1987)","journal-title":"Combinatorica"},{"key":"1522_CR6","unstructured":"Kitahara, T., Mizuno, Sh.: A proof by the simplex method for the diameter of a (0,1)-polytope. Optimization Online (2011)"},{"key":"1522_CR7","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, Sh: A bound for the number of different basic solutions generated by the simplex method. Math. Program. 137, 579\u2013586 (2013)","journal-title":"Math. Program."},{"key":"1522_CR8","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0012-365X(92)90349-K","volume":"102","author":"P Kleinschmidt","year":"1992","unstructured":"Kleinschmidt, P., Onn, S.: On the diameter of convex polytopes. Discrete Math. 102, 75\u201377 (1992)","journal-title":"Discrete Math."},{"key":"1522_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01589099","volume":"45","author":"D Naddef","year":"1989","unstructured":"Naddef, D.: The Hirsch conjecture is true for (0,1)-polytopes. Math. Program. Ser. A 45, 109\u2013110 (1989)","journal-title":"Math. Program. Ser. A"},{"key":"1522_CR10","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/S0097539703431007","volume":"33","author":"JB Orlin","year":"2004","unstructured":"Orlin, J.B., Punnen, A.P., Schulz, A.S.: Approximate local search in combinatorial optimization. SIAM J. Comput. 33, 1201\u20131214 (2004)","journal-title":"SIAM J. Comput."},{"key":"1522_CR11","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/3-540-60313-1_164","volume":"979","author":"AS Schulz","year":"1995","unstructured":"Schulz, A.S., Weismantel, R., Ziegler, G.M.: 0\/1-integer programming: optimization and augmentation are equivalent. Lect. Notes Comput. Sci. 979, 473\u2013483 (1995)","journal-title":"Lect. Notes Comput. Sci."},{"key":"1522_CR12","first-page":"399","volume-title":"Res. Trends Comb. Optim","author":"AS Schulz","year":"2009","unstructured":"Schulz, A.S.: On the relative complexity of 15 problems related to 0\/1-integer programming. In: Cook, W.J., Lov\u00e1sz, L., Vygen, J. (eds.) Res. Trends Comb. Optim, vol. 19, pp. 399\u2013428. Springer, Berlin (2009)"}],"updated-by":[{"DOI":"10.1007\/s10107-021-01682-7","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000}}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01522-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01522-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01522-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,9]],"date-time":"2021-10-09T22:40:19Z","timestamp":1633819219000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01522-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,4]]},"references-count":12,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1522"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01522-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,4]]},"assertion":[{"value":"24 August 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10107-021-01682-7","URL":"https:\/\/doi.org\/10.1007\/s10107-021-01682-7","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}