期刊
ACM TRANSACTIONS ON ALGORITHMS
卷 9, 期 4, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2500121
关键词
Stopping theory; secretary problem; online algorithms; competitive algorithms; submodular; matroid constraint; knapsack constraint
资金
- NSF CAREER award [1053605]
- ONR YIP award [N000141110662]
- DARPA/AFOSR [FA9550-12-1-0423]
- University of Maryland Research and Scholarship Award (RASA)
- NSF [CCF-1161626]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1053605] Funding Source: National Science Foundation
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) over tilde(root 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(root n)-competitive algorithm for the subadditive case. At the end, we consider some special cases of our general setting as well.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据