Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://link.springer.com/article/10.1007/s00453-013-9822-z below:

Online Unweighted Knapsack Problem with Removal Cost

In this paper, we study the online unweighted knapsack problem with removal cost. The input is a sequence of items u ₁,u ₂,…,u _n , each of which has a size and a value, where the value of each item is assumed to be equal to the size. Given the ith item u _i , we either put u _i into the knapsack or reject it with no cost. When u _i is put into the knapsack, some items in the knapsack are removed with removal cost if the sum of the size of u _i and the total size in the current knapsack exceeds the capacity of the knapsack. Here the removal cost means a cancellation charge or disposal fee. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack minus the total removal cost occurred.

In this paper, we consider two kinds of removal cost: unit and proportional cost. For both models, we provide their competitive ratios. Namely, we construct optimal online algorithms and prove that they are best possible.

This is a preview of subscription content, log in via an institution to check access.

Springer+ Basic

€34.99 /Month

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

1. Ashwinkumar, B.V.: Buyback problem - approximate matroid intersection with cancellation costs. In: Automata, Language and Programming. Lecture Notes in Computer Science, vol. 6755, pp. 379–390. Springer, Berlin (2011)

   Chapter  Google Scholar 

2. Ashwinkumar, B.V., Kleinberg, R.: Randomized online algorithms for the buyback problem. In: Internet and Network Economics. Lecture Notes in Computer Science, vol. 5929, pp. 529–536. Springer, Berlin (2009)

   Chapter  Google Scholar 

3. Babaioff, M., Hartline, J.D., Kleinberg, R.D.: Selling banner ads: online algorithms with buyback. In: Proceedings of the 4th Workshop on Ad Auctions (2008)

   Google Scholar 

4. Babaioff, M., Hartline, J.D., Kleinberg, R.D.: Selling ad campaigns: online algorithms with cancellations. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 61–70 (2009)

   Google Scholar 

5. Biyalogorsky, E., Carmon, Z., Fruchter, G.E., Gerstner, E.: Research note: overselling with opportunistic cancellations. Mark. Sci. 18(4), 605–610 (1999)

   Article  Google Scholar 

6. Constantin, F., Feldman, J., Muthukrishnan, S., Pál, M.: An online mechanism for ad slot reservations with cancellations. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1265–1274 (2009)

   Chapter  Google Scholar 

7. Han, X., Makino, K.: Online minimization knapsack problem. In: Approximation and Online Algorithms. Lecture Notes in Computer Science, vol. 5893, pp. 182–193. Springer, Berlin (2010)

   Chapter  Google Scholar 

8. Han, X., Makino, K.: Online removable knapsack with limited cuts. Theor. Comput. Sci. 411, 3956–3964 (2010)

   Article  MATH  MathSciNet  Google Scholar 

9. Iwama, K., Taketomi, S.: Removable online knapsack problems. In: Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 2380, pp. 293–305. Springer, Berlin (2002)

   Chapter  Google Scholar 

10. Iwama, K., Zhang, G.: Optimal resource augmentations for online knapsack. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science, vol. 4627, pp. 180–188. Springer, Berlin (2007)

    Chapter  Google Scholar 

11. Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)

    Book  MATH  Google Scholar 

12. Lueker, G.S.: Average-case analysis of off-line and on-line knapsack problems. J. Algorithms 29(2), 277–305 (1998)

    Article  MATH  MathSciNet  Google Scholar 

13. Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Program. 68, 73–104 (1995)

    MATH  MathSciNet  Google Scholar 

14. Noga, J., Sarbua, V.: An online partially fractional knapsack problem. In: Proceedings of 8th International Symposium on Parallel Architectures, Algorithms and Networks, pp. 108–112 (2005)

    Chapter  Google Scholar 

Download references

1. Software School, Dalian University of Technology, Dalian, China

   Xin Han

2. University of Tokyo, Tokyo, Japan

   Yasushi Kawase

3. Kyoto University, Kyoto, Japan

   Kazuhisa Makino

1. Xin Han
2. Yasushi Kawase
3. Kazuhisa Makino

Correspondence to Xin Han.

X. Han partially supported by NSFC(11101065) and “the Fundamental Research Funds for the Central Universities”.

Y. Kawase partially supported by the Global COE “The Research and Training Center for New Development in Mathematics.”

K. Makino partially supported by Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology of Japan.

Han, X., Kawase, Y. & Makino, K. Online Unweighted Knapsack Problem with Removal Cost. Algorithmica 70, 76–91 (2014). https://doi.org/10.1007/s00453-013-9822-z

Download citation

• Received: 07 October 2012

• Accepted: 05 August 2013

• Published: 27 August 2013

• Issue Date: September 2014

• DOI: https://doi.org/10.1007/s00453-013-9822-z

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4