Function Design for Improved Competitive Ratio in Online Resource Allocation with Procurement Costs

References

• Agrawal S, Devanur NR (2014) Fast algorithms for online stochastic convex programming. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1405–1424.Google Scholar
• Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Link, Google Scholar
• Andrews M, Antonakopoulos S, Zhang L (2016) Minimum-cost network design with (dis)economies of scale. SIAM J. Comput. 45(1):49–66.Google Scholar
• Azar Y, Buchbinder N, Chan TH, Chen S, Cohen IR, Gupta A, Huang Z, et al. (2016) Online algorithms for covering and packing problems with convex objectives. Proc. Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 148–157.Google Scholar
• Balcan MF, Blum A, Mansour Y (2008) Item pricing for revenue maximization. Proc. 9th ACM Conf. Electronic Commerce (ACM, New York), 50–59.Google Scholar
• Balcan MF, Blum A, Hartline JD, Mansour Y (2005) Mechanism design via machine learning. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci (IEEE, New York), 605–614.Google Scholar
• Bartal Y, Gonen R, Nisan N (2003) Incentive compatible multi unit combinatorial auctions. Proc. 9th Conf. Theoretical Aspects Rationality Knowledge (ACM, New York), 72–87.Google Scholar
• Bertsimas D, Hawkins J, Perakis G (2009) Optimal bidding in online auctions. J. Revenue Pricing Management 8(1):21–41.Google Scholar
• Blatter M, Muehlemann S, Schenker S (2012) The costs of hiring skilled workers. Eur. Econom. Rev. 56(1):20–35.Google Scholar
• Blum A, Gupta A, Mansour Y, Sharma A (2011) Welfare and profit maximization with production costs. Proc. Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ).Google Scholar
• Blumrosen L, Nisan N (2007) Combinatorial auctions. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 267–300.Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learn. 8(3–4):231–357.Google Scholar
• Buchbinder N, Naor JS (2009) The design of competitive online algorithms via a primal–dual approach. Foundations Trends Theoretical Comput. Sci. 3:93–263.Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Proc. Eur. Sympos. Algorithms (Springer, Berlin), 253–264.Google Scholar
• Chakraborty T, Huang Z, Khanna S (2013) Dynamic and nonuniform pricing strategies for revenue maximization. SIAM J. Comput. 42(6):2424–2451.Google Scholar
• Chan T, Huang Z, Kang N (2015) Online convex covering and packing problems. Preprint, submitted February 6, https://arxiv.org/abs/1502.01802.Google Scholar
• Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proc. 42nd ACM Sympos. Theory Comput. (ACM, New York), 311–320.Google Scholar
• Chow Y, Moriguti S, Robbins H, Samuels S (1964) Optimal selection based on relative rank (the “secretary problem”). Israel J. Math. 2(2):81–90.Google Scholar
• Devanur NR, Hayes TP (2009) The adwords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. Electronic Commerce (ACM, New York), 71–78.Google Scholar
• Devanur NR, Jain K (2012) Online matching with concave returns. Proc. 44th Annual ACM Sympos. Theory Comput. (ACM, New York), 137–144.Google Scholar
• Devanur NR, Jain K, Kleinberg RD (2013) Randomized primal-dual analysis of ranking for online bipartite matching. Proc. 24th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 101–107.Google Scholar
• Eghbali R, Fazel M (2016) Worst Case Competitive Analysis for Online Conic Optimization (Neural Information Processing Systems).Google Scholar
• Erdogan SA, Gose A, Denton BT (2015) Online appointment sequencing and scheduling. IIE Trans. 47(11):1267–1286.Google Scholar
• Gupta A, Mehta R, Molinaro M (2018) Maximizing profit with convex costs in the random-order model. Proc. 45th Internat. Colloquium Automata Languages Programming, Leibniz International Proceedings in Informatics, vol. 107, 71:1–71:14.Google Scholar
• Ho CJ, Vaughan JW (2012) Online task assignment in crowdsourcing markets. Proc. 26th AAAI Conf. Artificial Intelligence (AAAI Press, Cambridge, MA).Google Scholar
• Huang Z, Kim A (2018) Welfare maximization with production costs: A primal dual approach. Games Econom. Behav. 1:1–20.Google Scholar
• Hwang D, Jaillet P, Manshadi V (2021) Online resource allocation under partially predictable demand. Oper. Res. 69(3):895–915.Link, Google Scholar
• Jaillet P, Lu X (2012) Near-optimal online algorithms for dynamic resource allocation problems. Preprint, submitted August 13, https://arxiv.org/abs/1208.2596.Google Scholar
• Kalyanasundaram B, Pruhs KR (2000) An optimal deterministic algorithm for online b-matching. Theoretical Comput. Sci. 233(1–2):319–325.Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput. (ACM, New York), 352–358.Google Scholar
• Kesselheim T, Radke K, Tönnis A, Vöcking B (2013) An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. Proc. Eur. Sympos. Algorithms (Springer, Berlin), 589–600.Google Scholar
• Legrain A, Jaillet P (2013) Stochastic online bipartite resource allocation problems. Technical report, CIRRELT, Canada.Google Scholar
• Littlestone N, Warmuth MK (1994) The weighted majority algorithm. Inform. Comput. 108(2):212–261.Google Scholar
• Makarychev K, Sviridenko M (2014) Solving optimization problems with diseconomies of scale via decoupling. Proc. IEEE 55th Annual Sympos. Foundations Comput. Sci. (IEEE, New York), 571–580.Google Scholar
• McMahan B (2011) Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization. Proc. 14th Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 525–533.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoretical Comput. Sci. 8(4):265–368.Google Scholar
• Mehta A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching. J. ACM 54(5):19.Google Scholar
• Raut P, Sadeghi O, Fazel M (2021) Online DR-submodular maximization: Minimizing regret and constraint violation. Proc. Conf. AAAI Artificial Intelligence 35:9395–9402.Google Scholar
• Sadeghi O, Fazel M (2020) Online continuous DR-submodular maximization with long-term budget constraints. Proc. Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 4410–4419.Google Scholar
• Sadeghi O, Eghbali R, Fazel M (2020a) Online algorithms for budget-constrained dr-submodular maximization. Proc. ICML Workshop Negative Dependence Submodularity ML (MIT Press, Cambridge, MA).Google Scholar
• Sadeghi O, Raut P, Fazel M (2020b) A single recipe for online submodular maximization with adversarial or stochastic constraints. Adv. Neural Inform. Processing Systems 33:14712–14723.Google Scholar
• Sadeghi O, Raut P, Fazel M (2021) Improved regret bounds for online submodular maximization. Proc. ICML Workshop Subset Selection Machine Learn.: From Theory to Applications (ICML, San Diego).Google Scholar
• Tan X, Sun B, Leon-Garcia A, Wu Y, Tsang DH (2020) Mechanism design for online resource allocation: A unified approach. Proc. ACM Measurement Analysis Comput. Systems, vol. 4 (ACM, New York), 1–46.Google Scholar