We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of <Emphasis Type="BoldItalic">n</Emphasis> 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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10215_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{3/2}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn mathvariant="bold">3</mn> <mo mathvariant="bold" stretchy="false">/</mo> <mn mathvariant="bold">2</mn> </mrow> </math></EquationSource> </InlineEquation>. While this cannot be improved with fewer than <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10215_Article_IEq2.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{\log }_{\varvec{2}} \varvec{n} $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mo mathvariant="bold">log</mo> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msub> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation> advice bits for instances of length <Emphasis Type="BoldItalic">n</Emphasis>, a competitive ratio of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10215_Article_IEq3.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="37" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{1}\varvec{+}\varvec{\varepsilon }$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mn mathvariant="bold">1</mn> </mrow> <mrow> <mo mathvariant="bold">+</mo> </mrow> <mrow> <mi mathvariant="bold-italic">ε</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation> can be achieved with <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10215_Article_IEq4.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="144" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <msup> <mrow> <mi mathvariant="bold-italic">ε</mi> </mrow> <mrow> <mo mathvariant="bold">-</mo> <mn mathvariant="bold">1</mn> </mrow> </msup> <mrow> <mo mathvariant="bold">·</mo> </mrow> <mrow> <mo mathvariant="bold">log</mo> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <msup> <mrow> <mi mathvariant="bold-italic">ε</mi> </mrow> <mrow> <mo mathvariant="bold">-</mo> <mn mathvariant="bold">1</mn> </mrow> </msup> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> advice bits for any <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10215_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{\varepsilon }\varvec{>}\varvec{0}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">ε</mi> </mrow> <mrow> <mo mathvariant="bold">></mo> </mrow> <mrow> <mn mathvariant="bold">0</mn> </mrow> </mrow> </math></EquationSource> </InlineEquation>. We further show that no amount of advice bounded by a function <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10215_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{f(n)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">f</mi> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10215_Article_IEq7.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{\log }_{\varvec{2}} \varvec{n}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mo mathvariant="bold">log</mo> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msub> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation> advice bits. We also provide a surprisingly simple algorithm that uses <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10215_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="144" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <msup> <mrow> <mi mathvariant="bold-italic">ε</mi> </mrow> <mrow> <mo mathvariant="bold">-</mo> <mn mathvariant="bold">1</mn> </mrow> </msup> <mrow> <mo mathvariant="bold">·</mo> </mrow> <mrow> <mo mathvariant="bold">log</mo> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <msup> <mrow> <mi mathvariant="bold-italic">ε</mi> </mrow> <mrow> <mo mathvariant="bold">-</mo> <mn mathvariant="bold">1</mn> </mrow> </msup> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> advice bits to achieve a competitive ratio of <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10215_Article_IEq9.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="37" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{1}\varvec{+}\varvec{\varepsilon }$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mn mathvariant="bold">1</mn> </mrow> <mrow> <mo mathvariant="bold">+</mo> </mrow> <mrow> <mi mathvariant="bold-italic">ε</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation> for any <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10215_Article_IEq10.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$\varvec{\varepsilon }\varvec{>}\varvec{0}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">ε</mi> </mrow> <mrow> <mo mathvariant="bold">></mo> </mrow> <mrow> <mn mathvariant="bold">0</mn> </mrow> </mrow> </math></EquationSource> </InlineEquation>.

Online Unbounded Knapsack

期刊论文
出版模式：

开放获取
发表日期：

2025年3月1日

查看全文

Hans-Joachim Böckenhauer,
Matthias Gehnen,
Juraj Hromkovič,
Ralf Klasing,
Dennis Komm,
Henri Lotze,
Daniel Mock,
Peter Rossmanith,
Moritz Stocker

摘要

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}$ $3 / 2$ . While this cannot be improved with fewer than $\varvec{\log }_{\varvec{2}} \varvec{n} $ ${log}_{2} n$ advice bits for instances of length n, a competitive ratio of $\varvec{1}\varvec{+}\varvec{\varepsilon }$ $1 + ε$ can be achieved with $\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$ $O (ε^{- 1} \cdot log (n ε^{- 1}))$ advice bits for any $\varvec{\varepsilon }\varvec{>}\varvec{0}$ $ε > 0$ . We further show that no amount of advice bounded by a function $\varvec{f(n)}$ $f (n)$ 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}$ ${log}_{2} n$ 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{))}$ $O (ε^{- 1} \cdot log (n ε^{- 1}))$ advice bits to achieve a competitive ratio of $\varvec{1}\varvec{+}\varvec{\varepsilon }$ $1 + ε$ for any $\varvec{\varepsilon }\varvec{>}\varvec{0}$ $ε > 0$ .