More Web Proxy on the site http://driver.im/

Article

A Knapsack Secretary Problem with Applications

Authors:

Moshe Babaioff,

Nicole Immorlica,

Robert KleinbergAuthors Info & Claims

APPROX '07/RANDOM '07: Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques

Pages 16 - 28

https://doi.org/10.1007/978-3-540-74208-1_2

Published: 20 August 2007 Publication History

Abstract

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 <em>online knapsack problem</em>, is known to be inapproximable. Therefore, we make the enabling assumption that elements arrive in a <em>random</em>order. Hence our problem can be thought of as a weighted version of the classical <em>secretary problem</em>, which we call the <em>knapsack secretary problem</em>. Using the random-order assumption, we design a constant-competitive algorithm for arbitrary weights and values, as well as a <em>e</em>-competitive algorithm for the special case when all weights are equal (i.e., the <em>multiple-choice secretary problem</em>). 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.

References

[1]

Aggarwal, G., Hartline, J.: Knapsack auctions. In: SODA, pp. 1083-1092 (2006).

Digital Library

[2]

Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: SODA, pp. 434-443 (2007).

Digital Library

[3]

Borgs, C., Chayes, J., Etesami, O., Immorlica, N., Jain, K., Mahdian, M.: Dynamics of bid optimization in online advertisement auctions. In: Proceedings of the 16th International World Wide Web Conference, (to appear 2007).

Digital Library

[4]

Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing problems. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, Springer, Heidelberg (2005).

Digital Library

[5]

Buchbinder, N., Naor, J.: Improved bounds for online routing and packing via a primal-dual approach. In: FOCS (2006).

Digital Library

[6]

Chakrabarty, D., Zhou, Y., Lukose, R.: Budget constrained bidding in keyword auctions and online knapsack problems. In: WWW2007, Workshop on Sponsored Search Auctions (2007).

Digital Library

[7]

Dean, B., Goemans, M., Vondrák, J.: Approximating the stochastic knapsack problem: The benefit of adaptivity. In: FOCS, pp. 208-217 (2004).

Digital Library

[8]

Dean, B., Goemans, M., Vondrák, J.: Adaptivity and approximation for stochastic packing problems. In: SODA, pp. 395-404 (2005).

Digital Library

[9]

Dynkin, E.B.: The optimum choice of the instant for stopping a Markov process. Sov. Math. Dokl. 4 (1963).

[10]

Feldman, J., Muthukrishnan, S., Pal, M., Stein, C.: Budget optimization in searchbased advertising auctions. In: Proceedings of the 8th ACM Conference on Electronic Commerce, (to appear).

Digital Library

[11]

Kleinberg, R.: A multiple-choice secretary problem with applications to online auctions. In: SODA, pp. 630-631 (2005).

Digital Library

[12]

Lueker, G.: Average-case analysis of off-line and on-line knapsack problems. In: SODA, pp. 179-188 (1995).

Digital Library

[13]

Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Mathematical Programming 68, 73-104 (1995).

Digital Library

[14]

Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995).

Digital Library

[15]

Muthukrishnan, S., Pal, M., Svitkina, Z.: Stochastic models for budget optimization in search-based. manuscript (2007).

[16]

Rusmevichientong, P., Williamson, D.P.: An adaptive algorithm for selecting profitable keywords for search-based advertising services. In: Proceedings of the 7th ACM Conference on Electronic Commerce, ACM Press, New York (2006).

Digital Library

Cited By

Salem JGupta S(2024)Secretary Problems with Biased Evaluations Using Partial Ordinal InformationManagement Science10.1287/mnsc.2023.492670:8(5337-5366)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/mnsc.2023.4926
Hajiaghayi MKhani MPanigrahi DSpringer MKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Online algorithms for the santa claus problemProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602498(30732-30743)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602498
Abels ALadewig LSchewior KStinzendörfer M(2022)Knapsack Secretary Through BoostingApproximation and Online Algorithms10.1007/978-3-031-18367-6_4(61-81)Online publication date: 8-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-18367-6_4
Show More Cited By

A Knapsack Secretary Problem with Applications
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Knapsack Secretary Through Boosting
Approximation and Online Algorithms
Abstract
We revisit the knapsack-secretary problem (Babaioff et al.; APPROX 2007), a generalization of the classic secretary problem in which items have different sizes and multiple items may be selected if their total size does not exceed the capacity B ...
The online knapsack problem: Advice and randomization

We study the advice complexity and the random bit complexity of the online knapsack problem. Given a knapsack of unit capacity, and n items that arrive in successive time steps, an online algorithm has to decide for every item whether it gets packed ...
Submodular secretary problem and extensions
APPROX/RANDOM'10: Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

APPROX '07/RANDOM '07: Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques

August 2007

623 pages

ISBN:9783540742074

Editors:
Moses Charikar
Computer Science Dept., Princeton University, Princeton, USA NJ 08540-5233
,
Klaus Jansen
Institut für Informatik, Christian-Albrechts-Universität zu Kiel,, Kiel, Germany 24098
,
Omer Reingold
Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel 76100
,
José D. Rolim
Centre Universitaire d'Informatique,, Geneva, Switzerland 1227

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 20 August 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Salem JGupta S(2024)Secretary Problems with Biased Evaluations Using Partial Ordinal InformationManagement Science10.1287/mnsc.2023.492670:8(5337-5366)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/mnsc.2023.4926
Hajiaghayi MKhani MPanigrahi DSpringer MKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Online algorithms for the santa claus problemProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602498(30732-30743)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602498
Abels ALadewig LSchewior KStinzendörfer M(2022)Knapsack Secretary Through BoostingApproximation and Online Algorithms10.1007/978-3-031-18367-6_4(61-81)Online publication date: 8-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-18367-6_4
Boyar JFavrholdt LLarsen K(2021)Relative Worst-order AnalysisACM Computing Surveys10.1145/342591054:1(1-21)Online publication date: 2-Jan-2021
https://dl.acm.org/doi/10.1145/3425910
Bahrani MBeyhaghi HSingla SWeinberg S(2021)Formal Barriers to Simple Algorithms for the Matroid Secretary ProblemWeb and Internet Economics10.1007/978-3-030-94676-0_16(280-298)Online publication date: 14-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-94676-0_16
Giliberti JKarrenbauer A(2021)Improved Online Algorithm for Fractional Knapsack in the Random Order ModelApproximation and Online Algorithms10.1007/978-3-030-92702-8_12(188-205)Online publication date: 6-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-92702-8_12
Burjons EGehnen MLotze HMock DRossmanith P(2021)The Secretary Problem with Reservation CostsComputing and Combinatorics10.1007/978-3-030-89543-3_46(553-564)Online publication date: 24-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89543-3_46
Kumabe SMaehara T(2021)Prophet Secretary for k-Knapsack and l-Matroid Intersection via Continuous Exchange PropertyCombinatorial Algorithms10.1007/978-3-030-79987-8_30(428-441)Online publication date: 5-Jul-2021
https://dl.acm.org/doi/10.1007/978-3-030-79987-8_30
Karrenbauer AKovalevskaya E(2020)Reading Articles OnlineCombinatorial Optimization and Applications10.1007/978-3-030-64843-5_43(639-654)Online publication date: 11-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64843-5_43
Li SLi MDuan LLee V(2020)Online Maximum k-Interval Coverage ProblemCombinatorial Optimization and Applications10.1007/978-3-030-64843-5_31(455-470)Online publication date: 11-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64843-5_31
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents