{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T19:52:11Z","timestamp":1766087531105,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T00:00:00Z","timestamp":1553558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,3,26]]},"abstract":"<jats:p>This paper studies online optimization under inventory (budget) constraints. While online optimization is a well-studied topic, versions with inventory constraints have proven difficult. We consider a formulation of inventory-constrained optimization that is a generalization of the classic one-way trading problem and has a wide range of applications. We present a new algorithmic framework, \\textsfCR-Pursuit, and prove that it achieves the minimal competitive ratio among all deterministic algorithms (up to a problem-dependent constant factor) for inventory-constrained online optimization. Our algorithm and its analysis not only simplify and unify the state-of-the-art results for the standard one-way trading problem, but they also establish novel bounds for generalizations including concave revenue functions. For example, for one-way trading with price elasticity, the \\textsfCR-Pursuit algorithm achieves a competitive ratio that is within a small additive constant (i.e., 1\/3) to the lower bound of ln 0+1, where 0 is the ratio between the maximum and minimum base prices.<\/jats:p>","DOI":"10.1145\/3322205.3311081","type":"journal-article","created":{"date-parts":[[2020,3,26]],"date-time":"2020-03-26T13:12:37Z","timestamp":1585228357000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Competitive Online Optimization under Inventory Constraints"],"prefix":"10.1145","volume":"3","author":[{"given":"Qiulin","family":"Lin","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanling","family":"Yi","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Pang","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghua","family":"Chen","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Honig","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuanzhang","family":"Xiao","sequence":"additional","affiliation":[{"name":"University of Hawaii at Manoa, Honolulu, HI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Jacob D Abernethy Elad Hazan and Alexander Rakhlin. 2009. Competing in the dark: An efficient algorithm for bandit linear optimization. (2009).  Jacob D Abernethy Elad Hazan and Alexander Rakhlin. 2009. Competing in the dark: An efficient algorithm for bandit linear optimization. (2009)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSG.2013.2273800"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0436-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465533"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49529-2_6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"volume-title":"Gambling in a rigged casino: The adversarial multi-armed bandit problem","author":"Auer Peter","key":"e_1_2_1_7_1"},{"volume-title":"Online Algorithms for Covering and Packing Problems with Convex Objectives. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) . 148--157","year":"2016","author":"Azar Yossi","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1399589.1399596"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175351"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339123.2339126"},{"key":"e_1_2_1_12_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume":"40","author":"Bansal Nikhil","year":"2015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2012.6353691"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000024"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_61"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745854"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.05.034"},{"volume-title":"Optimal selection based on relative rank (the \"secretary problem\"). Israel Journal of mathematics","year":"1964","author":"Chow YS","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9156-9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213992"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105220"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/647371"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376159"},{"key":"e_1_2_1_27_1","unstructured":"Amos Fiat Yuval Rabani and Yiftach Ravid. 1990. Competitive k-server algorithms. (1990).  Amos Fiat Yuval Rabani and Yiftach Ravid. 1990. Competitive k-server algorithms. (1990)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189324"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9239-4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103448"},{"volume-title":"2016 IEEE 24th International Conference on Network Protocols (ICNP) . 1--10","author":"Guo Linqi","key":"e_1_2_1_31_1"},{"volume-title":"Joint Placement and Routing of Network Function Chains in Data Centers","author":"Guo Linqi","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","first-page":"58","article-title":"Automated online mechanism design and prophet inequalities","volume":"7","author":"Hajiaghayi Mohammad Taghi","year":"2007","journal-title":"AAAI"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5016-8"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988801"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762111"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.02.002"},{"volume-title":"Using Predictions in Online Optimization with Switching Costs: A Fast Algorithm and A Fundamental Limit. In IEEE Annual American Control Conference (ACC) . 3008--3013","year":"2018","author":"Li Yingying","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2226216"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2425248.2425275"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9217-8"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465551"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.241"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCS.2011.940571"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","DOI":"10.1109\/9.262032","volume-title":"Robust receding horizon control of constrained nonlinear systems","author":"Michalska Hanna","year":"1993"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057125"},{"volume-title":"IREP Symposium . 1--7.","year":"2017","author":"Pang John ZF","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2011.100411.100446"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2811374"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897540"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1997.2347"},{"volume-title":"2018 IEEE\/PES Transmission and Distribution Conference and Exposition . 1--5.","author":"Shafiee S.","key":"e_1_2_1_52_1"},{"key":"e_1_2_1_53_1","unstructured":"Shai Shalev-Shwartz and Sham M Kakade. 2009. Mind the duality gap: Logarithmic regret algorithms for online optimization. In Advances in Neural Information Processing Systems. 1457--1464.   Shai Shalev-Shwartz and Sham M Kakade. 2009. Mind the duality gap: Logarithmic regret algorithms for online optimization. In Advances in Neural Information Processing Systems. 1457--1464."},{"volume-title":"Proceedings of ACM SIGMETRICS .","year":"2017","author":"Yang Lin","key":"e_1_2_1_54_1"},{"volume-title":"Balancing Cost and Dissatisfaction in Online EV Charging under Real-time Pricing","author":"Hanling","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9344-4"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSG.2016.2551282"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311081","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322205.3311081","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:54Z","timestamp":1750206354000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322205.3311081"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,26]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,26]]}},"alternative-id":["10.1145\/3322205.3311081"],"URL":"https:\/\/doi.org\/10.1145\/3322205.3311081","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2019,3,26]]},"assertion":[{"value":"2019-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}