TY - GEN

T1 - Maximizing profit with convex costs in the random-order model

AU - Gupta, Anupam

AU - Mehta, Ruta

AU - Molinaro, Marco

N1 - Funding Information:
This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing. 1 Computer Science Department, Carnegie Mellon University, Pittsburgh, USA. Supported in part by NSF awards CCF-1536002, CCF-1540541, and CCF-1617790. 2 Supported in part by NSF award CCF-1750436, and the Simons Institute for the Theory of Computing. 3 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.
Funding Information:
∗ This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing. 1 Computer Science Department, Carnegie Mellon University, Pittsburgh, USA. Supported in part by NSF awards CCF-1536002, CCF-1540541, and CCF-1617790. 2 Supported in part by NSF award CCF-1750436, and the Simons Institute for the Theory of Computing. 3 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.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - 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.

AB - 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.

KW - Convex duality

KW - Online algorithms

KW - Random order

KW - Secretary problem

UR - http://www.scopus.com/inward/record.url?scp=85049776176&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049776176&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2018.71

DO - 10.4230/LIPIcs.ICALP.2018.71

M3 - Conference contribution

AN - SCOPUS:85049776176

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

A2 - Kaklamanis, Christos

A2 - Marx, Daniel

A2 - Chatzigiannakis, Ioannis

A2 - Sannella, Donald

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

Y2 - 9 July 2018 through 13 July 2018

ER -