Article

Removable Online Knapsack Problems

Authors:

Kazuo Iwama,

Shiro TaketomiAuthors Info & Claims

ICALP '02: Proceedings of the 29th International Colloquium on Automata, Languages and Programming

Pages 293 - 305

Published: 08 July 2002 Publication History

Abstract

We introduce an on-line model for a class of hand-making games such as Rummy and Mah-Jang. An input is a sequence of items, u ₁ , . . . , u _i , . . . such that 0 < | u _i | 1.0. When u _i is given, the on-line player puts it into the bin and can discard any selected items currently in the bin (including u _i ) under the condition that the total size of the remaining items is at most one. The goal is to make this total size as close to 1.0 as possible when the game ends. We also discuss the multibin model, where the player can select a bin out of the k ones which ui is put into. We prove tight bounds for the competitive ratio of this problem, both for k = 1 and k 2.

References

[1]

J. Csirik, G. Galambos, and G. Turán, "A lower bound on on-line algorithms for decreasing lists," Proc. EURO VI , 1984.

Google Scholar

[2]

J. Csirik, and G. Woeginger, "Resource argumentation for online bounded space bin packing," Proc. ICALP 2000 , pp. 296-304, 2000.

Crossref

Google Scholar

[3]

M. M. Halldórsson, "Online coloring known graphs," Electronic J. Combinatorics , Vol. 7, R7, 2000. www.combinatorics.org.

Google Scholar

[4]

M. M. Halldórsson, K. Iwama, S. Miyazaki, and S. Taketomi, "Online independent sets," Proc. COCOON 2000 , pp. 202-209, 2000.

Crossref

Google Scholar

[5]

D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham, "Worst-case performance bounds for simple one-dimensional packing algorithms," SIAM Journal on Computing , Vol. 3(4), pp. 299-325, 1974.

Google Scholar

[6]

G. S. Lueker, "Average-case analysis of off-line and on-line knapsack problems," Proc. Sixth Annual ACM-SIAM SODA , pp. 179-188, 1995.

Crossref

Google Scholar

[7]

A. Marchetti-Spaccamela and C. Vercellis, "Stochastic on-line knapsack problems," Math. Programming , Vol. 68(1, Ser. A), pp. 73-104, 1995.

Crossref

Google Scholar

[8]

S. S. Seiden, "On the online bin packing problem," Proc. ICALP 2001 , pp. 237-248, 2001.

Crossref

Google Scholar

[9]

S. S. Seiden, "An optimal online algorithm for bounded space variable-sized bin packing," Proc. ICALP 2000 , pp. 283-295, 2000.

Crossref

Google Scholar

[10]

A. van Vliet, "On the asymptotic worst case behavior of harmonic fit," J. Algorithms , Vol. 20, pp. 113-136, 1996.

Crossref

Google Scholar

Cited By

View all

Sun BZeynali ALi THajiesmaili MWierman ATsang D(2021)Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle ChargingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34283364:3(1-32)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3428336
Buchbinder NFeldman MSchwartz R(2019)Online Submodular Maximization with PreemptionACM Transactions on Algorithms10.1145/330976415:3(1-31)Online publication date: 7-Jun-2019
https://dl.acm.org/doi/10.1145/3309764
Chan THuang ZJiang SKang NTang Z(2018)Online Submodular Maximization with Free DisposalACM Transactions on Algorithms10.1145/324277014:4(1-29)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3242770
Show More Cited By

Removable Online Knapsack Problems
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

Online Knapsack Revisited

We investigate the online variant of the (Multiple) Knapsack Problem: an algorithm is to pack items, of arbitrary sizes and profits, in k knapsacks (bins) without exceeding the capacity of any bin. We study two objective functions: the sum and the ...
Removable Online Knapsack with Bounded Size Items
SOFSEM 2024: Theory and Practice of Computer Science
Abstract
In the online unweighted knapsack problem, some items arrive in sequence and one has to decide to pack them or not into a knapsack of given capacity. The objective is to maximize the total size of packed items. In the traditional setting, ... $\sqrt{}$
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICALP '02: Proceedings of the 29th International Colloquium on Automata, Languages and Programming

July 2002

1065 pages

ISBN:3540438645

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 July 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
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

View all

Sun BZeynali ALi THajiesmaili MWierman ATsang D(2021)Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle ChargingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34283364:3(1-32)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3428336
Buchbinder NFeldman MSchwartz R(2019)Online Submodular Maximization with PreemptionACM Transactions on Algorithms10.1145/330976415:3(1-31)Online publication date: 7-Jun-2019
https://dl.acm.org/doi/10.1145/3309764
Chan THuang ZJiang SKang NTang Z(2018)Online Submodular Maximization with Free DisposalACM Transactions on Algorithms10.1145/324277014:4(1-29)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3242770
Kawase YIwasaki A(2017)Near-feasible stable matchings with budget constraintsProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171678(242-248)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171642.3171678
Fukuda SShioura ATokuyama T(2017)Buyback problem with discrete concave valuation functionsDiscrete Optimization10.5555/3163581.316366026:C(78-96)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.5555/3163581.3163660
Chan THuang ZJiang SKang NTang ZKlein P(2017)Online submodular maximization with free disposalProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039764(1204-1223)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039764
Floratou AMegiddo NPotti NÖzcan FKale USchmitz-Hermes J(2016)Adaptive Caching in Big SQL using the HDFS CacheProceedings of the Seventh ACM Symposium on Cloud Computing10.1145/2987550.2987553(321-333)Online publication date: 5-Oct-2016
https://dl.acm.org/doi/10.1145/2987550.2987553
Buchbinder NFeldman MSchwartz RIndyk P(2015)Online submodular maximization with preemptionProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722209(1202-1216)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722209
Han XKawase YMakino K(2015)Randomized algorithms for online knapsack problemsTheoretical Computer Science10.1016/j.tcs.2014.10.017562:C(395-405)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.10.017
Kawase YHan XMakino K(2015)Proportional Cost Buyback Problem with Weight BoundsProceedings of the 9th International Conference on Combinatorial Optimization and Applications - Volume 948610.1007/978-3-319-26626-8_59(794-808)Online publication date: 18-Dec-2015
https://dl.acm.org/doi/10.1007/978-3-319-26626-8_59
Show More Cited By

Abstract

References

Cited By

Recommendations

Online Knapsack Revisited

Removable Online Knapsack with Bounded Size Items

The online knapsack problem: Advice and randomization

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations