{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:18:33Z","timestamp":1742912313123,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031069000"},{"type":"electronic","value":"9783031069017"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"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":[[2022]]},"DOI":"10.1007\/978-3-031-06901-7_12","type":"book-chapter","created":{"date-parts":[[2022,5,27]],"date-time":"2022-05-27T00:22:30Z","timestamp":1653610950000},"page":"154-167","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Simple Method for\u00a0Convex Optimization in the Oracle Model"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Dadush","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Hojny","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sophie","family":"Huiberts","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Weltge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,27]]},"reference":[{"issue":"1","key":"12_CR1","first-page":"1","volume":"69","author":"DS Atkinson","year":"1995","unstructured":"Atkinson, D.S., Vaidya, P.M.: A cutting plane algorithm for convex programming that uses analytic centers. Math. Program. 69(1), 1\u201343 (1995)","journal-title":"Math. Program."},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Badenbroek, R., de Klerk, E.: An analytic center cutting plane method to determine complete positivity of a matrix. INFORMS J. Comput. 34(2), 1115\u20131125 (2021)","DOI":"10.1287\/ijoc.2021.1108"},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"Beck, A.: First-Order Methods in Optimization. Society for Industrial and Applied Mathematics (2017). https:\/\/doi.org\/10.1137\/1.9781611974997","DOI":"10.1137\/1.9781611974997"},{"issue":"3","key":"12_CR4","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1287\/moor.1090.0388","volume":"34","author":"A Belloni","year":"2009","unstructured":"Belloni, A., Freund, R.M., Vempala, S.: An efficient rescaled perceptron algorithm for conic systems. Math. Oper. Res. 34(3), 621\u2013641 (2009)","journal-title":"Math. Oper. Res."},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization. Society for Industrial and Applied Mathematics (2001). https:\/\/doi.org\/10.1137\/1.9780898718829","DOI":"10.1137\/1.9780898718829"},{"issue":"3","key":"12_CR6","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s00454-004-2878-4","volume":"32","author":"U Betke","year":"2004","unstructured":"Betke, U.: Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem. Discrete Comput. Geom. 32(3), 317\u2013338 (2004). https:\/\/doi.org\/10.1007\/s00454-004-2878-4","journal-title":"Discrete Comput. Geom."},{"key":"12_CR7","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Quanrud, K.: Approximating the held-karp bound for metric TSP in nearly-linear time. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, October 2017. https:\/\/doi.org\/10.1109\/focs.2017.78","DOI":"10.1109\/focs.2017.78"},{"key":"12_CR8","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Quanrud, K.: Near-linear time approximation schemes for some implicit fractional packing problems. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, January 2017. https:\/\/doi.org\/10.1137\/1.9781611974782.51","DOI":"10.1137\/1.9781611974782.51"},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF01386389","volume":"1","author":"EW Cheney","year":"1959","unstructured":"Cheney, E.W., Goldstein, A.A.: Newton\u2019s method for convex programming and Tchebycheff approximation. Numer. Math. 1(1), 253\u2013268 (1959)","journal-title":"Numer. Math."},{"issue":"2","key":"12_CR10","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-011-0445-3","volume":"134","author":"S Chubanov","year":"2011","unstructured":"Chubanov, S.: A strongly polynomial algorithm for linear systems having a binary solution. Math. Program. 134(2), 533\u2013570 (2011). https:\/\/doi.org\/10.1007\/s10107-011-0445-3","journal-title":"Math. Program."},{"key":"12_CR11","unstructured":"Chubanov, S.: A polynomial algorithm for linear feasibility problems given by separation oracles. Optim. Online (2017)"},{"key":"12_CR12","unstructured":"Color02 - computational symposium: Graph coloring and its generalizations (2002). http:\/\/mat.gsia.cmu.edu\/COLOR02"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Dadush, D., Hojny, C., Huiberts, S., Weltge, S.: A simple method for convex optimization in the oracle model. arXiv:2011.08557 (2021). https:\/\/arxiv.org\/abs\/2011.08557","DOI":"10.1007\/978-3-031-06901-7_12"},{"issue":"2","key":"12_CR14","doi-asserted-by":"publisher","first-page":"732","DOI":"10.1287\/moor.2019.1011","volume":"45","author":"D Dadush","year":"2020","unstructured":"Dadush, D., V\u00e9gh, L.A., Zambelli, G.: Rescaling algorithms for linear conic feasibility. Math. Oper. Res. 45(2), 732\u2013754 (2020). https:\/\/doi.org\/10.1287\/moor.2019.1011","journal-title":"Math. Oper. Res."},{"key":"12_CR15","unstructured":"Dantzig, G.B.: Converting a converging algorithm into a polynomially bounded algorithm. Technical report, Stanford University, 1992. 5.6, 6.1, 6.5 (1991)"},{"issue":"1","key":"12_CR16","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1023\/A:1012470815092","volume":"46","author":"A Demiriz","year":"2002","unstructured":"Demiriz, A., Bennett, K.P., Shawe-Taylor, J.: Linear programming boosting via column generation. Mach. Learn. 46(1), 225\u2013254 (2002)","journal-title":"Mach. Learn."},{"issue":"1","key":"12_CR17","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s10107-007-0095-7","volume":"114","author":"J Dunagan","year":"2007","unstructured":"Dunagan, J., Vempala, S.: A simple polynomial-time rescaling algorithm for solving linear programs. Math. Program. 114(1), 101\u2013114 (2007). https:\/\/doi.org\/10.1007\/s10107-007-0095-7","journal-title":"Math. Program."},{"issue":"1\u20132","key":"12_CR18","first-page":"125","volume":"69B","author":"J Edmonds","year":"1964","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stand. 69B(1\u20132), 125\u2013130 (1964)","journal-title":"J. Res. Natl. Bur. Stand."},{"issue":"1\u20132","key":"12_CR19","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Q. 3(1\u20132), 95\u2013110 (1956)","journal-title":"Naval Res. Logist. Q."},{"issue":"2","key":"12_CR20","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1137\/s0097539704446232","volume":"37","author":"N Garg","year":"2007","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37(2), 630\u2013652 (2007). https:\/\/doi.org\/10.1137\/s0097539704446232","journal-title":"SIAM J. Comput."},{"issue":"6","key":"12_CR21","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995). https:\/\/doi.org\/10.1145\/227683.227684","journal-title":"J. ACM"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"RE Gomory","year":"1958","unstructured":"Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc. 64, 275\u2013278 (1958)","journal-title":"Bull. Amer. Math. Soc."},{"key":"12_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 2. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/978-3-642-78240-4"},{"key":"12_CR24","unstructured":"Jaggi, M.: Revisiting Frank-Wolfe: projection-free sparse convex optimization. In: Proceedings of Machine Learning Research, vol. 28, pp. 427\u2013435. PMLR, Atlanta, 17\u201319 June 2013. http:\/\/proceedings.mlr.press\/v28\/jaggi13.html"},{"key":"12_CR25","doi-asserted-by":"publisher","unstructured":"Jiang, H., Lee, Y.T., Song, Z., Wong, S.C.W.: An improved cutting plane method for convex optimization, convex-concave games, and its applications. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 944\u2013953. Association for Computing Machinery, New York (2020). https:\/\/doi.org\/10.1145\/3357713.3384284","DOI":"10.1145\/3357713.3384284"},{"issue":"4","key":"12_CR26","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0108053","volume":"8","author":"JE Kelley Jr","year":"1960","unstructured":"Kelley, J.E., Jr.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703\u2013712 (1960)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"12_CR27","unstructured":"Khachiyan, L.G.: A polynomial algorithm in linear programming (in russian). Doklady Akademiia Nauk SSSR 224 224, 1093\u20131096 (1979). English Translation: Soviet Mathematics Doklady 20, 191\u2013194"},{"key":"12_CR28","doi-asserted-by":"publisher","unstructured":"Lee, Y.T., Sidford, A., Wong, S.C.: A faster cutting plane method and its implications for combinatorial and convex optimization. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1049\u20131065 (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.68","DOI":"10.1109\/FOCS.2015.68"},{"key":"12_CR29","unstructured":"Nemirovsky, A., Yudin, D.: Informational complexity and efficient methods for solution of convex extremal problems. \u00c9kon. Math. Metody 12 (1983)"},{"issue":"1","key":"12_CR30","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s10107-003-0392-8","volume":"69","author":"Y Nesterov","year":"1995","unstructured":"Nesterov, Y.: Cutting plane algorithms from analytic centers: efficiency estimates. Math. Program. 69(1), 149\u2013176 (1995)","journal-title":"Math. Program."},{"issue":"2","key":"12_CR31","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"SA Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2), 257\u2013301 (1995). https:\/\/doi.org\/10.1287\/moor.20.2.257","journal-title":"Math. Oper. Res."},{"issue":"6","key":"12_CR32","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1037\/h0042519","volume":"65","author":"F Rosenblatt","year":"1958","unstructured":"Rosenblatt, F.: The perceptron: a probabilistic model for information storage and organization in the brain. Psychol. Rev. 65(6), 386\u2013408 (1958). https:\/\/doi.org\/10.1037\/h0042519","journal-title":"Psychol. Rev."},{"key":"12_CR33","doi-asserted-by":"publisher","unstructured":"Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. J. ACM 37(2), 318\u2013334 (1990). https:\/\/doi.org\/10.1145\/77600.77620, http:\/\/doi.acm.org\/10.1145\/77600.77620","DOI":"10.1145\/77600.77620"},{"key":"12_CR34","doi-asserted-by":"crossref","unstructured":"Sonnevend, G.: New algorithms in convex programming based on a notion of \u201ccentre\u201d (for systems of analytic inequalities) and on rational extrapolation. In: Hoffmann, K.H., Zowe, J., Hiriart-Urruty, J.B., Lemarechal, C. (eds.) Trends in Mathematical Optimization: 4th French-German Conference on Optimization, pp. 311\u2013326. Birkh\u00e4user Basel, Basel (1988)","DOI":"10.1007\/978-3-0348-9297-1_20"},{"key":"12_CR35","unstructured":"UC Irvine Machine Learning Repository. https:\/\/archive-beta.ics.uci.edu\/ml\/datasets. Accessed 3 Sept 2021"},{"issue":"3","key":"12_CR36","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/bf02592216","volume":"73","author":"PM Vaidya","year":"1996","unstructured":"Vaidya, P.M.: A new algorithm for minimizing convex functions over convex sets. Math. Program. 73(3), 291\u2013341 (1996). https:\/\/doi.org\/10.1007\/bf02592216","journal-title":"Math. Program."}],"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-06901-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T23:03:22Z","timestamp":1653951802000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-06901-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031069000","9783031069017"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-06901-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"27 May 2022","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":"Eindhoven","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.ipco2022.com\/home","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":"93","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":"35% - 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":"33","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)"}}]}}