IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v83y2016i2d10.1007_s00186-015-0526-9.html
   My bibliography  Save this article

The online knapsack problem with incremental capacity

Author

Listed:
  • Clemens Thielen

    (University of Kaiserslautern)

  • Morten Tiedemann

    (University of Göttingen)

  • Stephan Westphal

    (Clausthal University of Technology)

Abstract

We consider an online knapsack problem with incremental capacity. In each time period, a set of items, each with a specific weight and value, is revealed and, without knowledge of future items, it has to be decided which of these items to accept. Additionally, the knapsack capacity is not fully available from the start but increases by a constant amount in each time period. The goal is to maximize the overall value of the accepted items. This setting extends the basic online knapsack problem by introducing a dynamic instead of a static knapsack capacity and is applicable to classic problems such as resource allocation or one-way trading. In contrast to the basic online knapsack problem, for which no competitive algorithms exist, the setting of incremental capacity facilitates the development of competitive algorithms for a bounded time horizon. We provide a competitive analysis of deterministic and randomized online algorithms for the online knapsack problem with incremental capacity and present lower bounds on the competitive ratio achievable by online algorithms for the problem. Most of these lower bounds match the competitive ratios achieved by our online algorithms exactly or differ only by a constant factor.

Suggested Citation

  • Clemens Thielen & Morten Tiedemann & Stephan Westphal, 2016. "The online knapsack problem with incremental capacity," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 83(2), pages 207-242, April.
    • Handle: RePEc:spr:mathme:v:83:y:2016:i:2:d:10.1007_s00186-015-0526-9
    DOI: 10.1007/s00186-015-0526-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00186-015-0526-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00186-015-0526-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Richard Van Slyke & Yi Young, 2000. "Finite Horizon Stochastic Knapsacks with Applications to Yield Management," Operations Research, INFORMS, vol. 48(1), pages 155-172, February.
    2. Anton J. Kleywegt & Jason D. Papastavrou, 1998. "The Dynamic and Stochastic Knapsack Problem," Operations Research, INFORMS, vol. 46(1), pages 17-35, February.
    3. Jason D. Papastavrou & Srikanth Rajagopalan & Anton J. Kleywegt, 1996. "The Dynamic and Stochastic Knapsack Problem with Deadlines," Management Science, INFORMS, vol. 42(12), pages 1706-1718, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Alexander G. Nikolaev & Sheldon H. Jacobson, 2010. "Technical Note ---Stochastic Sequential Decision-Making with a Random Number of Jobs," Operations Research, INFORMS, vol. 58(4-part-1), pages 1023-1027, August.
    2. Clifford Stein & Van-Anh Truong & Xinshang Wang, 2020. "Advance Service Reservations with Heterogeneous Customers," Management Science, INFORMS, vol. 66(7), pages 2929-2950, July.
    3. Shelby Brumelle & Darius Walczak, 2003. "Dynamic Airline Revenue Management with Multiple Semi-Markov Demand," Operations Research, INFORMS, vol. 51(1), pages 137-148, February.
    4. Pak, K. & Dekker, R., 2004. "Cargo Revenue Management: Bid-Prices for a 0-1 Multi Knapsack Problem," ERIM Report Series Research in Management ERS-2004-055-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    5. Grace Y. Lin & Yingdong Lu & David D. Yao, 2008. "The Stochastic Knapsack Revisited: Switch-Over Policies and Dynamic Pricing," Operations Research, INFORMS, vol. 56(4), pages 945-957, August.
    6. Grace Lin & Yingdong Lu & David Yao, 2007. "Stochastic Knapsack Problem Revisited: Switch-Over Policies and Dynamic Pricing," Papers 0708.1146, arXiv.org.
    7. Feng, Youyi & Xiao, Baichun, 2006. "A continuous-time seat control model for single-leg flights with no-shows and optimal overbooking upper bound," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1298-1316, October.
    8. Keumseok Kang & J. George Shanthikumar & Kemal Altinkemer, 2016. "Postponable Acceptance and Assignment: A Stochastic Dynamic Programming Approach," Manufacturing & Service Operations Management, INFORMS, vol. 18(4), pages 493-508, October.
    9. Pak, K. & Piersma, N., 2002. "airline revenue management," ERIM Report Series Research in Management ERS-2002-12-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    10. So, Mee Chi & Thomas, Lyn C. & Huang, Bo, 2016. "Lending decisions with limits on capital available: The polygamous marriage problem," European Journal of Operational Research, Elsevier, vol. 249(2), pages 407-416.
    11. Pak, K. & Piersma, N., 2002. "Airline revenue management: an overview of OR techniques 1982-2001," Econometric Institute Research Papers EI 2002-03, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    12. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    13. Anton J. Kleywegt & Jason D. Papastavrou, 2001. "The Dynamic and Stochastic Knapsack Problem with Random Sized Items," Operations Research, INFORMS, vol. 49(1), pages 26-41, February.
    14. Jihyeok Jung & Chan-Oi Song & Deok-Joo Lee & Kiho Yoon, 2024. "Optimal Mechanism in a Dynamic Stochastic Knapsack Environment," Papers 2402.14269, arXiv.org.
    15. Guillermo Gallego & Michael Z. F. Li & Yan Liu, 2020. "Dynamic Nonlinear Pricing of Inventories over Finite Sales Horizons," Operations Research, INFORMS, vol. 68(3), pages 655-670, May.
    16. Alec Morton, 2006. "Structural properties of network revenue management models: An economic perspective," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(8), pages 748-760, December.
    17. Maclean, K.D.S. & Ødegaard, F., 2020. "Dynamic capacity allocation for group bookings in live entertainment," European Journal of Operational Research, Elsevier, vol. 287(3), pages 975-988.
    18. Chiang, David Ming-Huang & Wu, Andy Wei-Di, 2011. "Discrete-order admission ATP model with joint effect of margin and order size in a MTO environment," International Journal of Production Economics, Elsevier, vol. 133(2), pages 761-775, October.
    19. Tianke Feng & Joseph C. Hartman, 2015. "The dynamic and stochastic knapsack Problem with homogeneous‐sized items and postponement options," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(4), pages 267-292, June.
    20. Huanan Zhang & Cong Shi & Chao Qin & Cheng Hua, 2016. "Stochastic regret minimization for revenue management problems with nonstationary demands," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(6), pages 433-448, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:mathme:v:83:y:2016:i:2:d:10.1007_s00186-015-0526-9. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.