Submodular secretary problem and extensions

By MohammadHossein Bateni, M. Hajiaghayi, Morteza Zadimoghaddam. 2010

173 citations recorded by the source corpus.

Online auction is the essence of many modern markets, particularly networked markets, in which information about goods, agents, and outcomes is revealed over a period of time, and the agents must make irrevocable decisions without knowing future information. Optimal stopping theory, especially the classic secretary problem, is a powerful tool for analyzing such online scenarios which generally require optimizing an objective function over the input. The secretary problem and its generalization the multiple-choice secretary problem were under a thorough study in the literature. In this article, we consider a very general setting of the latter problem called the submodular secretary problem, in which the goal is to select k secretaries so as to maximize the expectation of a (not necessarily monotone) submodular function which defines efficiency of the selected secretarial group based on their overlapping skills. We present the first constant-competitive algorithm for this case. In a more general setting in which selected secretaries should form an independent (feasible) set in each of l given matroids as well, we obtain an O(l log2 r)-competitive algorithm generalizing several previous results, where r is the maximum rank of the matroids. Another generalization is to consider l knapsack constraints (i.e., a knapsack constraint assigns a nonnegative cost to each secretary, and requires that the total cost of all the secretaries employed be no more than a budget value) instead of the matroid constraints, for which we present an O(l)-competitive algorithm. In a sharp contrast, we show for a more general setting of subadditive secretary problem, there is no õ(√n)-competitive algorithm and thus submodular functions are the most general functions to consider for constant-competitiveness in our setting. We complement this result by giving a matching O(√n)-competitive algorithm for the subadditive case. At the end, we consider some special cases of our general setting as well.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications, Mathematical Optimization, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

In Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

Submodular Function Maximization (2014, background): “Gupta et al. (2010) and Bateni et al. (2010) provide constant competitive 6 algorithms for the uniform matroid (where F = { S ⊆ V : | S | ≤ k } for some k ).”
Prophet Secretary (2015, background): “The submodular secretary problem is introduced by Bateni, H ajiaghayi, and Zadimoghaddam [10].”
Streaming submodular maximization: massive data summarization on the fly (2014, background): “There is further related work on the submodular secretary problem [15, 4].”
How to crowdsource tasks truthfully without sacrificing utility: Online incentive mechanisms with budget constraint (2014, background): “It is because that any user has no incentive to report a later arrival time or an earlier departure time than its true arrival/departure time, since the user cannot perform any sensing task or obtain a payment after it departs.”
Online Submodular Maximization with Preemption (2015, unknown): “This relaxation leads to “secretary type” algorithms.”