Submodular secretary problems with extensions
Venue
ACM Transactions on Algorithms, vol. 9 (4) (2013)
Publication Year
2013
Authors
Mohammadhossein Bateni, MohammadTaghi Hajiaghayi, Morteza Zadimoghaddam
BibTeX
Abstract
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 log^2 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 o~(\sqrt 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(\sqrt n) competitive algorithm for
the subadditive case. At the end, we consider some special cases of our general
setting as well.
