# 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 deﬁnes efficiency of the selected secretarial
group based on their overlapping skills. We present the ﬁrst 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.