{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:12:24Z","timestamp":1784110344569,"version":"3.55.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,1,9]],"date-time":"2019-01-09T00:00:00Z","timestamp":1546992000000},"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":["J. ACM"],"published-print":{"date-parts":[[2019,2,28]]},"abstract":"<jats:p>\n            We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an\n            <jats:italic>unknown<\/jats:italic>\n            distribution at every step. We design a single algorithm that, for every possible underlying distribution, obtains a 1\u2212\u03f5 fraction of the profit obtained by an algorithm that knows the entire request sequence ahead of time. The factor \u03f5 approaches 0 when no single request consumes\/contributes a significant fraction of the global consumption\/contribution by all requests together. We show that the tradeoff we obtain here that determines how fast \u03f5 approaches 0, is near optimal: We give a nearly matching lower bound showing that the tradeoff cannot be improved much beyond what we obtain.\n          <\/jats:p>\n          <jats:p>\n            Going beyond the model of a static underlying distribution, we introduce the\n            <jats:italic>adversarial stochastic input<\/jats:italic>\n            model, where an adversary, possibly in an adaptive manner, controls the distributions from which the requests are drawn at each step. Placing no restriction on the adversary, we design an algorithm that obtains a 1\u2212\u03f5 fraction of the optimal profit obtainable w.r.t. the worst distribution in the adversarial sequence. Further, if the algorithm is given one number per distribution, namely the optimal profit possible for each of the adversary\u2019s distribution, then we design an algorithm that achieves a 1\u2212\u03f5 fraction of the weighted average of the optimal profit of each distribution the adversary picks.\n          <\/jats:p>\n          <jats:p>\n            In the offline setting we give a fast algorithm to solve very large linear programs (LPs) with both packing and covering constraints. We give algorithms to approximately solve (within a factor of 1+\u03f5) the mixed packing-covering problem with\n            <jats:italic>O<\/jats:italic>\n            (\u03b3\n            <jats:italic>m<\/jats:italic>\n            log (\n            <jats:italic>n<\/jats:italic>\n            \/\u03b4)\/\u03f5\n            <jats:sup>2<\/jats:sup>\n            ) oracle calls where the constraint matrix of this LP has dimension\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>m<\/jats:italic>\n            , the success probability of the algorithm is 1\u2212\u03b4, and \u03b3 quantifies how significant a single request is when compared to the sum total of all requests.\n          <\/jats:p>\n          <jats:p>We discuss implications of our results to several special cases including online combinatorial auctions, network routing, and the adwords problem.<\/jats:p>","DOI":"10.1145\/3284177","type":"journal-article","created":{"date-parts":[[2019,1,9]],"date-time":"2019-01-09T18:36:36Z","timestamp":1547058996000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems"],"prefix":"10.1145","volume":"66","author":[{"given":"Nikhil R.","family":"Devanur","sequence":"first","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kamal","family":"Jain","sequence":"additional","affiliation":[{"name":"Faira, Redmond, Kirkland, WA,USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0188-7622","authenticated-orcid":false,"given":"Balasubramanian","family":"Sivan","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christopher A.","family":"Wilkens","sequence":"additional","affiliation":[{"name":"Facebook Research, Menlo Park, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,1,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA\u201915)","author":"Agrawal Shipra"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2765026.2765038"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229018"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778606"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807362"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566384"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229043"},{"key":"e_1_2_1_9_1","unstructured":"R. Eghbali J. Swenson and M. Fazel. 2014. Exponentiated subgradient algorithm for online optimization under the random permutation model. ArXiv e-prints1410.7171 (Oct. 2014).  R. Eghbali J. Swenson and M. Fazel. 2014. Exponentiated subgradient algorithm for online optimization under the random permutation model. ArXiv e-prints1410.7171 (Oct. 2014)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888935.1888957"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796457"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Goel Gagan","year":"2008"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_43"},{"key":"e_1_2_1_15_1","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"Kalyanasundaram Bala"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the S7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201996)","author":"Kamath Anil","year":"1996"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627905"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591810"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185411"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313689"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875556"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284177","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3284177","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:01Z","timestamp":1750208881000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,9]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,28]]}},"alternative-id":["10.1145\/3284177"],"URL":"https:\/\/doi.org\/10.1145\/3284177","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,9]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}