Document Open Access Logo

Maximizing Profit with Convex Costs in the Random-order Model

Authors Anupam Gupta, Ruta Mehta, Marco Molinaro

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.71.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Anupam Gupta
  • Carnegie Mellon University, Pittsburgh, USA
Ruta Mehta
  • University of Illinois Urbana-Champaign, Champaign, USA
Marco Molinaro
  • PUC-Rio, Rio de Janeiro, Brazil

Funding

  • Gupta, Anupam: Computer Science Department, Carnegie Mellon University, Pittsburgh, USA. Supported in part by NSF awards CCF-1536002, CCF-1540541, and CCF-1617790.
  • Mehta, Ruta: Supported in part by NSF award CCF-1750436, and the Simons Institute for the Theory of Computing.
  • Molinaro, Marco: Supported in part by CNPq grants Universal #431480/2016-8 and Bolsa de Produtividade em Pesquisa #310516/2017-0, and a Microsoft Research Fellowship at the Simons Institute for the Theory of Computing.

Cite As Get BibTex

Anupam Gupta, Ruta Mehta, and Marco Molinaro. Maximizing Profit with Convex Costs in the Random-order Model. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.71

Abstract

Suppose a set of requests arrives online: each request gives some value v_i if accepted, but requires using some amount of each of d resources. Our cost is a convex function of the vector of total utilization of these d resources. Which requests should be accept to maximize our profit, i.e., the sum of values of the accepted demands, minus the convex cost?
We consider this problem in the random-order a.k.a. secretary model, and show an O(d)-competitive algorithm for the case where the convex cost function is also supermodular. If the set of accepted demands must also be independent in a given matroid, we give an O(d^3 alpha)-competitive algorithm for the supermodular case, and an improved O(d^2 alpha) if the convex cost function is also separable. Here alpha is the competitive ratio of the best algorithm for the submodular secretary problem. These extend and improve previous results known for this problem. Our techniques are simple but use powerful ideas from convex duality, which give clean interpretations of existing work, and allow us to give the extensions and improvements.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online algorithms
  • secretary problem
  • random order
  • convex duality

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Shipra Agrawal and Nikhil R. Devanur. Fast algorithms for online stochastic convex programming. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1405-1424. SIAM, Philadelphia, PA, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.93.
  2. Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Oper. Res., 62(4):876-890, 2014. URL: http://dx.doi.org/10.1287/opre.2014.1289.
  3. Yossi Azar, Niv Buchbinder, T-H. Hubert Chan, Shahar Chen, Ilan R. Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph (Seffi) Naor, and Debmalya Panigrahi. Online algorithms for covering and packing problems with convex objectives. In 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016, New Brunswick, NJ, USA, October 9-11, 2016, 2016. Google Scholar
  4. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In APPROX-RANDOM, pages 16-28, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74208-1_2.
  5. Siddharth Barman, Seeun Umboh, Shuchi Chawla, and David Malec. Secretary problems with convex costs. In Automata, languages, and programming. Part I, volume 7391 of Lecture Notes in Comput. Sci., pages 75-87. Springer, Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_7.
  6. Avrim Blum, Anupam Gupta, Yishay Mansour, and Ankit Sharma. Welfare and profit maximization with production costs. In FOCS, pages 77-86, Nov 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.68.
  7. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Adaptivity and approximation for stochastic packing problems. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 395-404, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070487.
  8. Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In Yoav Shoham, Yan Chen, and Tim Roughgarden, editors, ACM Conference on Electronic Commerce, pages 29-38. ACM, 2011. URL: http://dx.doi.org/10.1145/1993574.1993581.
  9. Reza Eghbali and Maryam Fazel. Designing smoothing functions for improved worst-case competitive ratio in online optimization. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 3279-3287, 2016. URL: http://papers.nips.cc/paper/6073-designing-smoothing-functions-for-improved-worst-case-competitive-ratio-in-online-optimization.
  10. Reza Eghbali, Jon Swenson, and Maryam Fazel. Exponentiated subgradient algorithm for online optimization under the random permutation model. CoRR, abs/1410.7171, 2014. URL: http://arxiv.org/abs/1410.7171,
  11. Moran Feldman, Ola Svensson, and Rico Zenklusen. A simple O(log log(rank))-competitive algorithm for the matroid secretary problem. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1189-1201. SIAM, Philadelphia, PA, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.79.
  12. Moran Feldman and Rico Zenklusen. The submodular secretary problem goes linear. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science - FOCS 2015, pages 486-505. IEEE Computer Soc., Los Alamitos, CA, 2015. Google Scholar
  13. P. R. Freeman. The secretary problem and its extensions: a review. Internat. Statist. Rev., 51(2):189-206, 1983. URL: http://dx.doi.org/10.2307/1402748.
  14. Anupam Gupta and Marco Molinaro. How the experts algorithm can help solve lps online. Math. Oper. Res., 41(4):1404-1431, 2016. URL: http://dx.doi.org/10.1287/moor.2016.0782.
  15. Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal. Fundamentals of convex analysis. Grundlehren Text Editions. Springer-Verlag, Berlin, 2001. URL: http://dx.doi.org/10.1007/978-3-642-56468-0.
  16. Zhiyi Huang and Anthony Kim. Welfare maximization with production costs: a primal dual approach. In 26th SODA, pages 59-72. SIAM, Philadelphia, PA, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.6.
  17. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal beats dual on online packing LPs in the random-order model. In STOC'14 - Proceedings of the 2014 ACM Symposium on Theory of Computing, pages 303-312. ACM, New York, 2014. Google Scholar
  18. Robert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, SODA '05, pages 630-631, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics. URL: http://portal.acm.org/citation.cfm?id=1070432.1070519.
  19. Oded Lachish. O(log log rank) competitive ratio for the matroid secretary problem. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 326-335, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.42.
  20. Marco Molinaro and R. Ravi. The geometry of online packing linear programs. Math. Oper. Res., 39(1):46-59, 2014. URL: http://dx.doi.org/10.1287/moor.2013.0612.
  21. Donald M. Topkis. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact