2007 | OriginalPaper | Buchkapitel
A Knapsack Secretary Problem with Applications
verfasst von : Moshe Babaioff, Nicole Immorlica, David Kempe, Robert Kleinberg
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider situations in which a decision-maker with a fixed budget faces a sequence of options, each with a cost and a value, and must select a subset of them online so as to maximize the total value. Such situations arise in many contexts, e.g., hiring workers, scheduling jobs, and bidding in sponsored search auctions.
This problem, often called the
online knapsack problem
, is known to be inapproximable. Therefore, we make the enabling assumption that elements arrive in a
random
order. Hence our problem can be thought of as a weighted version of the classical
secretary problem
, which we call the
knapsack secretary problem
. Using the random-order assumption, we design a constant-competitive algorithm for arbitrary weights and values, as well as a
e
-competitive algorithm for the special case when all weights are equal (i.e., the
multiple-choice secretary problem
). In contrast to previous work on online knapsack problems, we do not assume any knowledge regarding the distribution of weights and values beyond the fact that the order is random.