{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T10:03:30Z","timestamp":1766484210449,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"InnoHK Initiative"},{"name":"Laboratory for AI-Powered Financial Technologies"},{"name":"Hong Kong Research Grants Council","award":["9043143"],"award-info":[{"award-number":["9043143"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2022,5,26]]},"abstract":"<jats:p>We study an online inventory trading problem where a user seeks to maximize the aggregate revenue of trading multiple inventories over a time horizon. The trading constraints and concave revenue functions are revealed sequentially in time, and the user needs to make irrevocable decisions. The problem has wide applications in various engineering domains. Existing works employ the primal-dual framework to design online algorithms with sub-optimal, albeit near-optimal, competitive ratios (CR). We exploit the problem structure to develop a new divide-and-conquer approach to solve the online multi-inventory problem by solving multiple calibrated single-inventory ones separately and combining their solutions. The approach achieves the optimal CR of \u0142n \u03b8 + 1 if N\u0142eq \u0142n \u03b8 + 1, where N is the number of inventories and \u03b8 represents the revenue function uncertainty; it attains a CR of 1\/[1-e^-1\/(\u0142n\u03b8+1) ] in [\u0142n \u03b8 +1, \u0142n \u03b8 +2) otherwise. The divide-and-conquer approach reveals novel structural insights for the problem, (partially) closes a gap in existing studies, and generalizes to broader settings. For example, it gives an algorithm with a CR within a constant factor to the lower bound for a generalized one-way trading problem with price elasticity with no previous results. When developing the above results, we also extend a recent CR-Pursuit algorithmic framework and introduce an online allocation problem with allowance augmentation, both of which can be of independent interest.<\/jats:p>","DOI":"10.1145\/3530902","type":"journal-article","created":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T17:16:18Z","timestamp":1654535778000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Competitive Online Optimization with Multiple Inventories"],"prefix":"10.1145","volume":"6","author":[{"given":"Qiulin","family":"Lin","sequence":"first","affiliation":[{"name":"City University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanfang","family":"Mo","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junyan","family":"Su","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghua","family":"Chen","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2699290"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQoS.2018.8624184"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2021.3114537"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSTE.2018.2810274"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494232.2465551"},{"key":"e_1_2_1_6_1","volume-title":"Peak-aware online economic dispatching for microgrids","author":"Zhang Ying","year":"2016","unstructured":"Ying Zhang , Mohammad H Hajiesmaili , Sinan Cai , Minghua Chen , and Qi Zhu . Peak-aware online economic dispatching for microgrids . IEEE transactions on smart grid, 9(1):323--335, 2016 . Ying Zhang, Mohammad H Hajiesmaili, Sinan Cai, Minghua Chen, and Qi Zhu. Peak-aware online economic dispatching for microgrids. IEEE transactions on smart grid, 9(1):323--335, 2016."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447555.3464857"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOMWKSHPS51825.2021.9484511"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2226216"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.241"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8486362"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8486429"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1643707"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_63"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2425248.2425275"},{"key":"e_1_2_1_18_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Bansal Nikhil","year":"2015","unstructured":"Nikhil Bansal , Anupam Gupta , Ravishankar Krishnaswamy , Kirk Pruhs , Kevin Schewior , and Cliff Stein . A 2-competitive algorithm for online convex optimization with switching costs . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2015 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik , 2015. Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Cliff Stein. A 2-competitive algorithm for online convex optimization with switching costs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_34"},{"key":"e_1_2_1_20_1","first-page":"137","volume-title":"Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12","author":"Nikhil","year":"2012","unstructured":"Nikhil R. Devanur and Kamal Jain. Online matching with concave returns . In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12 , page 137 -- 144 , New York, NY, USA , 2012 . Association for Computing Machinery. Nikhil R. Devanur and Kamal Jain. Online matching with concave returns. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12, page 137--144, New York, NY, USA, 2012. Association for Computing Machinery."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3309697.3331495"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428336"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1190-x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00140-1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2794394"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1957"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.7"},{"key":"e_1_2_1_28_1","volume-title":"A unified approach to online allocation algorithms via randomized dual fitting. CoRR, abs\/1308.5444","author":"Niazadeh Rad","year":"2013","unstructured":"Rad Niazadeh and Robert D. Kleinberg . A unified approach to online allocation algorithms via randomized dual fitting. CoRR, abs\/1308.5444 , 2013 . Rad Niazadeh and Robert D. Kleinberg. A unified approach to online allocation algorithms via randomized dual fitting. CoRR, abs\/1308.5444, 2013."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9217-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.24"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2917393"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2170092"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462067"}],"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\/3530902","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3530902","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:27Z","timestamp":1750183767000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530902"}},"subtitle":["A Divide-and-Conquer Approach"],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,5,26]]}},"alternative-id":["10.1145\/3530902"],"URL":"https:\/\/doi.org\/10.1145\/3530902","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"2022-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}