License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.71
URN: urn:nbn:de:0030-drops-90751
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9075/
Go to the corresponding LIPIcs Volume Portal

Gupta, Anupam ; Mehta, Ruta ; Molinaro, Marco

Maximizing Profit with Convex Costs in the Random-order Model

pdf-format:
LIPIcs-ICALP-2018-71.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{gupta_et_al:LIPIcs:2018:9075,
  author =	{Anupam Gupta and Ruta Mehta and Marco Molinaro},
  title =	{{Maximizing Profit with Convex Costs in the Random-order Model}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9075},
  URN =		{urn:nbn:de:0030-drops-90751},
  doi =		{10.4230/LIPIcs.ICALP.2018.71},
  annote =	{Keywords: Online algorithms, secretary problem, random order, convex duality}
}

Keywords: Online algorithms, secretary problem, random order, convex duality
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI