{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T16:17:01Z","timestamp":1791908221774,"version":"4.3.4"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000},"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":["Math. Program."],"published-print":{"date-parts":[[2023,7]]},"DOI":"10.1007\/s10107-022-01880-x","type":"journal-article","created":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T19:03:41Z","timestamp":1661886221000},"page":"831-875","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Simple and fast algorithm for binary integer and online linear programming"],"prefix":"10.1007","volume":"200","author":[{"given":"Xiaocheng","family":"Li","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7389-4808","authenticated-orcid":false,"given":"Chunlin","family":"Sun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yinyu","family":"Ye","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,8,30]]},"reference":[{"key":"1880_CR1","unstructured":"Li, X., Sun, C., Ye, Y.: Simple and fast algorithm for binary integer and online linear programming. In: NeurIPS (2020)"},{"issue":"3","key":"1880_CR2","first-page":"282","volume":"4","author":"TS Ferguson","year":"1989","unstructured":"Ferguson, T.S., et al.: Who solved the secretary problem? Stat. Sci. 4(3), 282\u2013289 (1989)","journal-title":"Stat. Sci."},{"key":"1880_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack problems. Springer, Berlin, Heidelberg (2004)"},{"key":"1880_CR4","volume-title":"Linear Programming","author":"RJ Vanderbei","year":"2015","unstructured":"Vanderbei, R.J., et al.: Linear Programming. Springer, Boston, MA (2015)"},{"key":"1880_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer Programming","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G., et al.: Integer Programming, vol. 271. Springer, Cham (2014)"},{"issue":"2","key":"1880_CR6","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"key":"1880_CR7","doi-asserted-by":"crossref","unstructured":"Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized on-line matching. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905), pp. 264\u2013273 (2005). IEEE","DOI":"10.1109\/SFCS.2005.12"},{"issue":"1","key":"1880_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1287\/mnsc.5.1.97","volume":"5","author":"LR Ford Jr","year":"1958","unstructured":"Ford, L.R., Jr., Fulkerson, D.R.: A suggested computation for maximal multi-commodity network flows. Manage. Sci. 5(1), 97\u2013101 (1958)","journal-title":"Manage. Sci."},{"key":"1880_CR9","doi-asserted-by":"crossref","unstructured":"Dantzig, G.B.: Linear programming and extensions (1963)","DOI":"10.7249\/R366"},{"issue":"3","key":"1880_CR10","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1287\/moor.1040.0094","volume":"29","author":"DP De Farias","year":"2004","unstructured":"De Farias, D.P., Van Roy, B.: On constraint sampling in the linear programming approach to approximate dynamic programming. Math. Oper. Res. 29(3), 462\u2013478 (2004)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1880_CR11","doi-asserted-by":"publisher","first-page":"1185","DOI":"10.1109\/TAC.2017.2743163","volume":"63","author":"C Lakshminarayanan","year":"2017","unstructured":"Lakshminarayanan, C., Bhatnagar, S., Szepesv\u00e1ri, C.: A linearly relaxed approximate linear program for markov decision processes. IEEE Trans. Autom. Control 63(4), 1185\u20131191 (2017)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"4","key":"1880_CR12","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1287\/moor.2017.0894","volume":"43","author":"K Vu","year":"2018","unstructured":"Vu, K., Poirion, P.-L., Liberti, L.: Random projections for linear programming. Math. Oper. Res. 43(4), 1051\u20131071 (2018)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1880_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-003-0499-y","volume":"102","author":"G Calafiore","year":"2005","unstructured":"Calafiore, G., Campi, M.C.: Uncertain convex programs: randomized solutions and confidence levels. Math. Program. 102(1), 25\u201346 (2005)","journal-title":"Math. Program."},{"key":"1880_CR14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974997","volume-title":"First-order Methods in Optimization","author":"A Beck","year":"2017","unstructured":"Beck, A.: First-order Methods in Optimization, vol. 25. SIAM, Philadelphia, PA (2017)"},{"key":"1880_CR15","unstructured":"Yen, I.E.-H., Zhong, K., Hsieh, C.-J., Ravikumar, P.K., Dhillon, I.S.: Sparse linear programming via primal and dual augmented coordinate descent. In: Advances in Neural Information Processing Systems, pp. 2368\u20132376 (2015)"},{"key":"1880_CR16","unstructured":"Wang, S., Shroff, N.: A new alternating direction method for linear programming. In: Advances in Neural Information Processing Systems, pp. 1480\u20131488 (2017)"},{"key":"1880_CR17","unstructured":"Lin, T., Ma, S., Ye, Y., Zhang, S.: An admm-based interior-point method for large-scale linear programming. arXiv preprint arXiv:1805.12344 (2018)"},{"issue":"1","key":"1880_CR18","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1287\/moor.2013.0612","volume":"39","author":"M Molinaro","year":"2013","unstructured":"Molinaro, M., Ravi, R.: The geometry of online packing linear programs. Math. Oper. Res. 39(1), 46\u201359 (2013)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1880_CR19","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1287\/opre.2014.1289","volume":"62","author":"S Agrawal","year":"2014","unstructured":"Agrawal, S., Wang, Z., Ye, Y.: A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4), 876\u2013890 (2014)","journal-title":"Oper. Res."},{"key":"1880_CR20","doi-asserted-by":"crossref","unstructured":"Kesselheim, T., T\u00f6nnis, A., Radke, K., V\u00f6cking, B.: Primal beats dual on online packing lps in the random-order model. In: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, pp. 303\u2013312 (2014). ACM","DOI":"10.1145\/2591796.2591810"},{"key":"1880_CR21","doi-asserted-by":"crossref","unstructured":"Gupta, A., Molinaro, M.: How experts can solve lps online. In: European Symposium on Algorithms, pp. 517\u2013529 (2014). Springer","DOI":"10.1007\/978-3-662-44777-2_43"},{"key":"1880_CR22","unstructured":"Li, X., Ye, Y.: Online linear programming: Dual convergence, new algorithms, and regret bounds. arXiv preprint arXiv:1909.05499 (2019)"},{"issue":"6","key":"1880_CR23","doi-asserted-by":"publisher","first-page":"1312","DOI":"10.1287\/opre.2013.1216","volume":"61","author":"S Jasin","year":"2013","unstructured":"Jasin, S., Kumar, S.: Analysis of deterministic lp-based booking limit and bid price controls for revenue management. Oper. Res. 61(6), 1312\u20131320 (2013)","journal-title":"Oper. Res."},{"issue":"4","key":"1880_CR24","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1287\/opre.2015.1390","volume":"63","author":"S Jasin","year":"2015","unstructured":"Jasin, S.: Performance of an lp-based control for revenue management with unknown demand parameters. Oper. Res. 63(4), 909\u2013915 (2015)","journal-title":"Oper. Res."},{"key":"1880_CR25","unstructured":"Bumpensanti, P., Wang, H.: A re-solving heuristic with uniformly bounded loss for network revenue management. arXiv preprint arXiv:1802.06192 (2018)"},{"key":"1880_CR26","unstructured":"Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 630\u2013631 (2005). Society for Industrial and Applied Mathematics"},{"key":"1880_CR27","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1287\/stsy.2018.0028","volume":"9","author":"A Arlotto","year":"2019","unstructured":"Arlotto, A., Gurvich, I.: Uniformly bounded regret in the multisecretary problem. Stochastic Systems. 9, 231\u2013260 (2019)","journal-title":"Stochastic Systems."},{"key":"1880_CR28","doi-asserted-by":"crossref","unstructured":"Zhou, Y., Chakrabarty, D., Lukose, R.: Budget constrained bidding in keyword auctions and online knapsack problems. In: International Workshop on Internet and Network Economics, pp. 566\u2013576 (2008). Springer","DOI":"10.1007\/978-3-540-92185-1_63"},{"issue":"9","key":"1880_CR29","doi-asserted-by":"publisher","first-page":"3952","DOI":"10.1287\/mnsc.2018.3174","volume":"65","author":"SR Balseiro","year":"2019","unstructured":"Balseiro, S.R., Gur, Y.: Learning in repeated auctions with budgets: Regret minimization and equilibrium. Manage. Sci. 65(9), 3952\u20133968 (2019)","journal-title":"Manage. Sci."},{"key":"1880_CR30","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1287\/mnsc.2018.3220","volume":"66","author":"A Asadpour","year":"2019","unstructured":"Asadpour, A., Wang, X., Zhang, J.: Online resource allocation with limited flexibility. Manage. Sci. 66, 642\u2013666 (2019)","journal-title":"Manage. Sci."},{"key":"1880_CR31","doi-asserted-by":"publisher","unstructured":"Jiang, J., Zhang, J.: Online resource allocation with stochastic resource consumption (2019). https:\/\/doi.org\/10.13140\/RG.2.2.27542.09287","DOI":"10.13140\/RG.2.2.27542.09287"},{"key":"1880_CR32","unstructured":"Lu, H., Balseiro, S., Mirrokni, V.: Dual mirror descent for online allocation problems. arXiv preprint arXiv:2002.10421 (2020)"},{"issue":"Sep","key":"1880_CR33","first-page":"2503","volume":"13","author":"M Mahdavi","year":"2012","unstructured":"Mahdavi, M., Jin, R., Yang, T.: Trading regret for efficiency: online convex optimization with long term constraints. J. Mach. Learn. Res. 13(Sep), 2503\u20132528 (2012)","journal-title":"J. Mach. Learn. Res."},{"key":"1880_CR34","unstructured":"Yu, H., Neely, M., Wei, X.: Online convex optimization with stochastic constraints. In: Advances in Neural Information Processing Systems, pp. 1428\u20131438 (2017)"},{"key":"1880_CR35","unstructured":"Yuan, J., Lamperski, A.: Online convex optimization for cumulative constraints. In: Advances in Neural Information Processing Systems, pp. 6137\u20136146 (2018)"},{"key":"1880_CR36","doi-asserted-by":"crossref","unstructured":"Agrawal, S., Devanur, N.R.: Fast algorithms for online stochastic convex programming. In: Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1405\u20131424 (2014). SIAM","DOI":"10.1137\/1.9781611973730.93"},{"key":"1880_CR37","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10107-019-01440-w","volume":"186","author":"M G\u00fcrb\u00fczbalaban","year":"2021","unstructured":"G\u00fcrb\u00fczbalaban, M., Ozdaglar, A., Parrilo, P.: Why randomreshuffling beats stochastic gradient descent. Math. Program. 186, 49\u201384 (2021). https:\/\/doi.org\/10.1007\/s10107-019-01440-w","journal-title":"Math. Program."},{"key":"1880_CR38","doi-asserted-by":"crossref","unstructured":"Ying, B., Yuan, K., Sayed, A.H.: Convergence of variance-reduced learning under random reshuffling. In: 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2286\u20132290 (2018). IEEE","DOI":"10.1109\/ICASSP.2018.8461739"},{"key":"1880_CR39","unstructured":"Safran, I., Shamir, O.: How good is sgd with random shuffling? arXiv preprint arXiv:1908.00045 (2019)"},{"key":"1880_CR40","unstructured":"Gao, W., Sun, C., Ye, Y., Ye, Y.: Boosting method in approximately solving linear programming with fast online algorithm. arXiv preprint arXiv:2107.03570 (2021)"},{"issue":"3\u20134","key":"1880_CR41","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1561\/2400000013","volume":"2","author":"E Hazan","year":"2016","unstructured":"Hazan, E.: Introduction to online convex optimization. Foundations and Trends in Optimization 2(3\u20134), 157\u2013325 (2016)","journal-title":"Foundations and Trends in Optimization"},{"key":"1880_CR42","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 71\u201378 (2009). ACM","DOI":"10.1145\/1566374.1566384"},{"issue":"2","key":"1880_CR43","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A Panconesi","year":"1997","unstructured":"Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds. SIAM J. Comput. 26(2), 350\u2013368 (1997)","journal-title":"SIAM J. Comput."},{"key":"1880_CR44","doi-asserted-by":"crossref","unstructured":"Tolstikhin, I., Zhivotovskiy, N., Blanchard, G.: Permutational rademacher complexity. In: International Conference on Algorithmic Learning Theory, pp. 209\u2013223 (2015). Springer","DOI":"10.1007\/978-3-319-24486-0_14"},{"key":"1880_CR45","unstructured":"Moulines, E., Bach, F.R.: Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In: Advances in Neural Information Processing Systems, pp. 451\u2013459 (2011)"},{"key":"1880_CR46","unstructured":"Lacoste-Julien, S., Schmidt, M., Bach, F.: A simpler approach to obtaining an o (1\/t) convergence rate for the projected stochastic subgradient method. arXiv preprint arXiv:1212.2002 (2012)"},{"issue":"Oct","key":"1880_CR47","first-page":"2543","volume":"11","author":"L Xiao","year":"2010","unstructured":"Xiao, L.: Dual averaging methods for regularized stochastic learning and online optimization. J. Mach. Learn. Res. 11(Oct), 2543\u20132596 (2010)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"1880_CR48","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1287\/10-SSY010","volume":"4","author":"A Juditsky","year":"2014","unstructured":"Juditsky, A., Nesterov, Y.: Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization. Stochastic Systems 4(1), 44\u201380 (2014)","journal-title":"Stochastic Systems"},{"key":"1880_CR49","unstructured":"Flammarion, N., Bach, F.: From averaging to acceleration, there is only a step-size. In: Conference on Learning Theory, pp. 658\u2013695 (2015)"},{"key":"1880_CR50","unstructured":"Lei, L., Jordan, M.I.: On the adaptivity of stochastic gradient-based optimization. arXiv preprint arXiv:1904.04480 (2019)"},{"issue":"1","key":"1880_CR51","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1023\/A:1009642405419","volume":"4","author":"PC Chu","year":"1998","unstructured":"Chu, P.C., Beasley, J.E.: A genetic algorithm for the multidimensional knapsack problem. Journal of heuristics 4(1), 63\u201386 (1998)","journal-title":"Journal of heuristics"},{"issue":"1","key":"1880_CR52","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1162\/EVCO_a_00145","volume":"24","author":"JH Drake","year":"2016","unstructured":"Drake, J.H., \u00d6zcan, E., Burke, E.K.: A case study of controlling crossover in a selection hyper-heuristic framework using the multidimensional knapsack problem. Evol. Comput. 24(1), 113\u2013141 (2016)","journal-title":"Evol. Comput."},{"key":"1880_CR53","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2545-2","volume-title":"Weak Convergence and Empirical Processes (Springer Series in Statistics)","author":"JWA van der Vaart","year":"1996","unstructured":"van der Vaart, J.W.A.: Weak Convergence and Empirical Processes (Springer Series in Statistics). Springer, New York, NY (1996)"},{"key":"1880_CR54","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding Machine Learning: From Theory to Algorithms","author":"S Shalev-Shwartz","year":"2014","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, Cambridge (2014)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01880-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01880-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01880-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T21:14:25Z","timestamp":1727903665000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01880-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,30]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1880"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01880-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,30]]},"assertion":[{"value":"9 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}