{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T23:03:54Z","timestamp":1768086234408,"version":"3.49.0"},"publisher-location":"Cham","reference-count":43,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030589417","type":"print"},{"value":"9783030589424","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-58942-4_2","type":"book-chapter","created":{"date-parts":[[2020,9,18]],"date-time":"2020-09-18T06:03:58Z","timestamp":1600409038000},"page":"22-38","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Restarting Algorithms: Sometimes There Is Free Lunch"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Pokutta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,19]]},"reference":[{"key":"2_CR1","unstructured":"Allen-Zhu, Z., Orecchia, L.: Linear coupling: An ultimate unification of gradient and mirror descent. arXiv preprint \narXiv:1407.1537\n\n (2014)"},{"key":"2_CR2","unstructured":"Anari, N., Haghtalab, N., Naor, S., Pokutta, S., Singh, M., Torrico, A.: Structured robust submodular maximization: offline and online algorithms. In: Proceedings of AISTATS (2019)"},{"key":"2_CR3","unstructured":"Anari, N., Haghtalab, N., Naor, S., Pokutta, S., Singh, M., Torrico, A.: Structured robust submodular maximization: offline and online algorithms. INFORMS J. Comput. (2020+, to appear)"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Anderson, D., Hendel, G., Le Bodic, P., Viernickel, M.: Clairvoyant restarts in branch-and-bound search using online tree-size estimation. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 1427\u20131434 (2019)","DOI":"10.1609\/aaai.v33i01.33011427"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1497\u20131514. SIAM (2014)","DOI":"10.1137\/1.9781611973402.110"},{"key":"2_CR6","unstructured":"Berthold, T., Heinz, S., Pfetsch, M.E.: Solving pseudo-Boolean problems with SCIP (2008)"},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-540-79719-7_4","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2008","author":"A Biere","year":"2008","unstructured":"Biere, A.: Adaptive restart strategies for conflict driven SAT solvers. In: Kleine B\u00fcning, H., Zhao, X. (eds.) SAT 2008. LNCS, vol. 4996, pp. 28\u201333. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-79719-7_4"},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0166-218X(99)00156-0","volume":"98","author":"A Bockmayr","year":"1999","unstructured":"Bockmayr, A., Eisenbrand, F., Hartmann, M., Schulz, A.: On the Chv\u00e1tal rank of polytopes in the 0\/1 cube. Discrete Appl. Math. 98, 21\u201327 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"2_CR9","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1137\/050644641","volume":"17","author":"J Bolte","year":"2007","unstructured":"Bolte, J., Daniilidis, A., Lewis, A.: The \u0142ojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205\u20131223 (2007)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2_CR10","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s10107-016-1091-6","volume":"165","author":"J Bolte","year":"2016","unstructured":"Bolte, J., Nguyen, T.P., Peypouquet, J., Suter, B.W.: From error bounds to the complexity of first-order descent methods for convex functions. Math. Program. 165(2), 471\u2013507 (2016). \nhttps:\/\/doi.org\/10.1007\/s10107-016-1091-6","journal-title":"Math. Program."},{"key":"2_CR11","unstructured":"Braun, G., Pokutta, S., Zink, D.: Lazifying conditional gradient algorithms. In: Proceedings of the International Conference on Machine Learning (ICML) (2017)"},{"issue":"71","key":"2_CR12","first-page":"1","volume":"20","author":"G Braun","year":"2019","unstructured":"Braun, G., Pokutta, S., Zink, D.: Lazifying conditional gradient algorithms. J. Mach. Learn. Res. (JMLR) 20(71), 1\u201342 (2019)","journal-title":"J. Mach. Learn. Res. (JMLR)"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4, 305\u2013337 (1973)","journal-title":"Discrete Math."},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0024-3795(89)90476-X","volume":"114","author":"V Chv\u00e1tal","year":"1989","unstructured":"Chv\u00e1tal, V., Cook, W., Hartmann, M.: On cutting-plane proofs in combinatorial optimization. Linear algebra Appl. 114, 455\u2013499 (1989)","journal-title":"Linear algebra Appl."},{"key":"2_CR15","unstructured":"Combettes, C.W., Pokutta, S.: Revisiting the Approximate Carath\u00e9odory Problem via the Frank-Wolfe Algorithm. Preprint (2019)"},{"key":"2_CR16","unstructured":"Diakonikolas, J., Carderera, A., Pokutta, S.: Locally accelerated conditional gradients. Proceedings of AISTATS (\narXiv:1906.07867\n\n) (2020, to appear)"},{"issue":"2","key":"2_CR17","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248\u2013264 (1972)","journal-title":"J. ACM"},{"issue":"2","key":"2_CR18","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00493-003-0020-5","volume":"23","author":"F Eisenbrand","year":"2003","unstructured":"Eisenbrand, F., Schulz, A.: Bounds on the Chv\u00e1tal rank on polytopes in the 0\/1-cube. Combinatorica 23(2), 245\u2013261 (2003)","journal-title":"Combinatorica"},{"key":"2_CR19","doi-asserted-by":"publisher","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions\u2013ii. In: Balinski, M.L., Hoffman, A.J. (eds.) Polyhedral Combinatorics, pp. 73\u201387. Springer, Heidelberg (1978). \nhttps:\/\/doi.org\/10.1007\/BFb0121195","DOI":"10.1007\/BFb0121195"},{"key":"2_CR20","unstructured":"Graham, R.L., Gr\u00f6tschel, M., Lov\u00e1sz, L.: Handbook of Combinatorics, vol.\u00a01. Elsevier (1995)"},{"key":"2_CR21","unstructured":"Hazan, E.: Lecture notes: Optimization for machine learning. arXiv preprint \narXiv:1909.03550\n\n (2019)"},{"key":"2_CR22","unstructured":"Hazan, E., Luo, H.: Variance-reduced and projection-free stochastic optimization. In: International Conference on Machine Learning, pp. 1263\u20131271 (2016)"},{"key":"2_CR23","unstructured":"Hinder, O., Lubin, M.: A generic adaptive restart scheme with applications to saddle point algorithms. arXiv preprint \narXiv:2006.08484\n\n (2020)"},{"key":"2_CR24","unstructured":"Hu, X., Shonkwiler, R., Spruill, M.C.: Random restarts in global optimization (2009)"},{"key":"2_CR25","first-page":"2318","volume":"7","author":"J Huang","year":"2007","unstructured":"Huang, J., et al.: The effect of restarts on the efficiency of clause learning. IJCAI 7, 2318\u20132323 (2007)","journal-title":"IJCAI"},{"key":"2_CR26","unstructured":"Johnson, R., Zhang, T.: Accelerating stochastic gradient descent using predictive variance reduction. In: Advances in Neural Information Processing Systems, pp. 315\u2013323 (2013)"},{"key":"2_CR27","unstructured":"Kerdreux, T., d\u2019Aspremont, A., Pokutta, S.: Restarting Frank-Wolfe. In: Proceedings of AISTATS (2019)"},{"key":"2_CR28","unstructured":"Lan, G., Pokutta, S., Zhou, Y., Zink, D.: Conditional accelerated lazy stochastic gradient descent. In: Proceedings of the International Conference on Machine Learning (ICML) (2017)"},{"key":"2_CR29","doi-asserted-by":"publisher","unstructured":"Lan, G.: First-order and Stochastic Optimization Methods for Machine Learning. Springer, Heidelberg (2020). \nhttps:\/\/doi.org\/10.1007\/978-3-030-39568-1","DOI":"10.1007\/978-3-030-39568-1"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disopt.2017.08.004","volume":"27","author":"P Le Bodic","year":"2018","unstructured":"Le Bodic, P., Pfetsch, M., Pavelka, J., Pokutta, S.: Solving MIPs via scaling-based augmentation. Discrete Optim. 27, 1\u201325 (2018)","journal-title":"Discrete Optim."},{"key":"2_CR31","unstructured":"Mirrokni, V., Paes Leme, R., Vladu, A., Wong, S.C.W.: Tight bounds for approximate Carath\u00e9odory and beyond. In: Proceedings of the 34th International Conference on Machine Learning, pp. 2440\u20132448 (2017)"},{"issue":"1","key":"2_CR32","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions\u2013I. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"2_CR33","unstructured":"Nemirovski, A.: Lectures on modern convex optimization. In: Society for Industrial and Applied Mathematics (SIAM). Citeseer (2001)"},{"key":"2_CR34","first-page":"10","volume":"88","author":"Y Nesterov","year":"2012","unstructured":"Nesterov, Y.: How to make the gradients small. Optima. Math. Optim. Soc. Newslett. 88, 10\u201311 (2012)","journal-title":"Optima. Math. Optim. Soc. Newslett."},{"key":"2_CR35","doi-asserted-by":"publisher","unstructured":"Nesterov, Y.: Lectures on Convex Optimization. Springer, Heidelberg (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-319-91578-4","DOI":"10.1007\/978-3-319-91578-4"},{"key":"2_CR36","first-page":"543","volume":"269","author":"YE Nesterov","year":"1983","unstructured":"Nesterov, Y.E.: A method for solving the convex programming problem with convergence rate $$O(1\/k^2)$$. Dokl. akad. nauk Sssr. 269, 543\u2013547 (1983)","journal-title":"Dokl. akad. nauk Sssr."},{"key":"2_CR37","unstructured":"O\u2019donoghue, B., Candes, E.: Adaptive restart for accelerated gradient schemes. Found. Comput. Math. 15(3), 715\u2013732 (2015)"},{"issue":"1","key":"2_CR38","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1287\/opre.2016.1549","volume":"65","author":"T Rothvo\u00df","year":"2017","unstructured":"Rothvo\u00df, T., Sanit\u00e0, L.: 0\/1 polytopes with quadratic chv\u00e1tal rank. Oper. Res. 65(1), 212\u2013220 (2017)","journal-title":"Oper. Res."},{"key":"2_CR39","unstructured":"Roulet, V., d\u2019Aspremont, A.: Sharpness, restart and acceleration. ArXiv preprint \narXiv:1702.03828\n\n (2017)"},{"issue":"4","key":"2_CR40","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1287\/moor.27.4.681.305","volume":"27","author":"AS Schulz","year":"2002","unstructured":"Schulz, A.S., Weismantel, R.: The complexity of generic primal algorithms for solving general integer programs. Math. Oper. Res. 27(4), 681\u2013692 (2002)","journal-title":"Math. Oper. Res."},{"key":"2_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/3-540-60313-1_164","volume-title":"Algorithms \u2014 ESA \u201995","author":"AS Schulz","year":"1995","unstructured":"Schulz, A.S., Weismantel, R., Ziegler, G.M.: 0\/1-integer programming: optimization and augmentation are equivalent. In: Spirakis, P. (ed.) ESA 1995. LNCS, vol. 979, pp. 473\u2013483. Springer, Heidelberg (1995). \nhttps:\/\/doi.org\/10.1007\/3-540-60313-1_164"},{"key":"2_CR42","unstructured":"Scieur, D., d\u2019Aspremont, A., Bach, F.: Regularized nonlinear acceleration. In: Advances in Neural Information Processing Systems, pp. 712\u2013720 (2016)"},{"key":"2_CR43","unstructured":"Xu, Y., Yang, T.: Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition (2018)"}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-58942-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,18]],"date-time":"2020-09-18T06:05:23Z","timestamp":1600409123000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-58942-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030589417","9783030589424"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-58942-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"19 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vienna","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cpaior2020.dbai.tuwien.ac.at\/","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":"72","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":"25","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":"7","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.08","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":"3.08","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)"}}]}}