Online Unbounded Knapsack

Abstract We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of n items with a size and a value each, and an algorithm has to decide whether or not and how often to pack each item into a knapsack of bounded capacity. The items are given online and the total size of the packed items must not exceed the knapsack’s capacity, while the objective is to maximize the total value of the packed items. While each item can only be packed once in the classical knapsack problem (also called the 0-1 knapsack problem), the unbounded version allows for items to be packed multiple times. We show that the simple unbounded knapsack problem, where the size of each item is equal to its value, allows for a competitive ratio of 2. We also analyze randomized algorithms and show that, in contrast to the 0-1 knapsack problem, one uniformly random bit cannot improve an algorithm’s performance. More randomness lowers the competitive ratio to less than 1 . 736 , but it can never be below 1 . 693 . In the advice complexity setting, we measure how many bits of information (so-called advice bits) the algorithm has to know to achieve some desired solution quality. For the simple unbounded knapsack problem, one advice bit lowers the competitive ratio to $$\varvec{3/2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> . While this cannot be improved with fewer than $$\varvec{\log }_{\varvec{2}} \varvec{n} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mo>log</mml:mo> </mml:mrow> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msub> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:mrow> </mml:math> advice bits for instances of length n , a competitive ratio of $$\varvec{1}\varvec{+}\varvec{\varepsilon }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mn>1</mml:mn> </mml:mrow> <mml:mrow> <mml:mo>+</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>ε</mml:mi> </mml:mrow> </mml:mrow> </mml:math> can be achieved with $$\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>O</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:msup> <mml:mrow> <mml:mi>ε</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mrow> <mml:mo>·</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>log</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:msup> <mml:mrow> <mml:mi>ε</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mrow> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> advice bits for any $$\varvec{\varepsilon }\varvec{&gt;}\varvec{0}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>ε</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>&gt;</mml:mo> </mml:mrow> <mml:mrow> <mml:mn>0</mml:mn> </mml:mrow> </mml:mrow> </mml:math> . We further show that no amount of advice bounded by a function $$\varvec{f(n)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> allows an algorithm to be optimal. We also study the online general unbounded knapsack problem and show that it does not allow for any bounded competitive ratio for both deterministic and randomized algorithms, as well as for algorithms using fewer than $$\varvec{\log }_{\varvec{2}} \varvec{n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mo>log</mml:mo> </mml:mrow> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msub> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:mrow> </mml:math> advice bits. We also provide a surprisingly simple algorithm that uses $$\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>O</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:msup> <mml:mrow> <mml:mi>ε</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mrow> <mml:mo>·</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>log</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:msup> <mml:mrow> <mml:mi>ε</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mrow> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> advice bits to achieve a competitive ratio of <jats:tex