Paper Info
Title
Online Knapsack Problems with Limited Cuts
Abstract
The (offline) maximization (resp., minimization) knapsack problem is given a set of items with weights and sizes, and the capacity of a knapsack, to maximize (resp., minimize) the total weight of selected items under the constraint that the total size of the selected items is at most (resp., at least) the capacity of the knapsack. In this paper, we study online maximization and minimization knapsack problems with limited cuts, in which 1) items are given one by one over time, i.e., after a decision is made on the current item, the next one is given, 2) items are allowed to be cut at most k ( 驴 1) times, and 3) items are allowed to be removed from the knapsack.We obtain the following three results. For the maximization knapsack problem, we propose a (k + 1)/k-competitive online algorithm, and show that it is the best possible, i.e., no online algorithm can have a competitive ratio less than (k + 1)/k. For the minimization knapsack problem, we show that no online algorithm can have a constant competitive ratio. We extend the result (i) to the resource augmentation model, where an online algorithm is allowed to use a knapsack of capacity m ( 1), while the optimal algorithm uses a unit capacity knapsack.
Year
DOI
Venue
2009
10.1007/978-3-642-10631-6_36
ISAAC
Keywords
Field
DocType
selected item,limited cuts,online maximization,knapsack problem,online algorithm,unit capacity knapsack,optimal algorithm,minimization knapsack problem,maximization knapsack problem,online knapsack problems,capacity m,k-competitive online algorithm,competitive ratio
Online algorithm,Combinatorics,Mathematical optimization,Change-making problem,Continuous knapsack problem,Cutting stock problem,Knapsack problem,Polynomial-time approximation scheme,Maximization,Mathematics,Competitive analysis
Conference
Volume
ISSN
Citations 
5878
0302-9743
1
PageRank 
References 
Authors
0.35
11
2
Name
Order
Citations
PageRank
Xin Han121324.49
Kazuhisa Makino21088102.74