Maximizing profit with convex costs in the random-order model

Anupam Gupta, Ruta Mehta, Marco Molinaro

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Suppose a set of requests arrives online: each request gives some value vi 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(d3α)-competitive algorithm for the supermodular case, and an improved O(d2α) if the convex cost function is also separable. Here α 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.

Original languageEnglish (US)
Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
EditorsChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770767
DOIs
StatePublished - Jul 1 2018
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: Jul 9 2018Jul 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume107
ISSN (Print)1868-8969

Other

Other45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
CountryCzech Republic
CityPrague
Period7/9/187/13/18

Keywords

  • Convex duality
  • Online algorithms
  • Random order
  • Secretary problem

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Maximizing profit with convex costs in the random-order model'. Together they form a unique fingerprint.

  • Cite this

    Gupta, A., Mehta, R., & Molinaro, M. (2018). Maximizing profit with convex costs in the random-order model. In C. Kaklamanis, D. Marx, I. Chatzigiannakis, & D. Sannella (Eds.), 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 [71] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 107). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2018.71