We introduce the Online Unbounded Knapsack Problem with Removal, a variation of the well-known Online Knapsack Problem. Items, each with a weight and value, arrive online and an algorithm must decide on whether or not to pack them into a knapsack with a fixed weight limit. An item may be packed an arbitrary number of times and items may be removed from the knapsack at any time without cost. The goal is to maximize the total value of items packed, while respecting a weight limit. We show that this is one of the very few natural online knapsack variants that allow for competitive deterministic algorithms in the general setting, by providing an algorithm with competitivity 1.6911. We complement this with a lower bound of 1.5877. We also analyze the proportional setting, where the weight and value of any single item agree, and show that deterministic algorithms can be exactly 3/2-competitive. Lastly, we give lower and upper bounds of 6/5 and 4/3 on the competitivity of randomized algorithms in this setting.

We survey the current state of research on the knapsack problem in online and semi-online environments. In particular, we summarize what is known about models where different assumptions commonly made in online computation are relaxed: namely that online algorithms do not know the complete instances they are processing; have to make decisions that are irrevocable; and deal with an input chosen by a malicious adversary.

Graph coloring is a notoriously challenging problem, especially when considering the online setting where each arriving vertex must be colored immediately and irreversibly. Even on trees, which are trivially two-colorable, achieving anything better than a logarithmic competitive ratio becomes impossible if the order of arrival is adversarially determined. We investigate tree coloring in a slightly relaxed model where vertices arrive online but in random order, focusing specifically on algorithms with predictions of varying reliability. Furthermore, we extend our analysis to all two-colorable graphs and provide matching lower bounds for both cases.

We analyze the competitive ratio of the proportional online knapsack problem with removal and limited recourse. In contrast to the classical online knapsack problem, packed items can be removed and a limited number of removed items can be re-inserted to the knapsack. The variant with removal only was analyzed by Iwama and Taketomi (ICALP, 2002). We show that even a single use of recourse can improve the performance of an algorithm. We give lower bounds for a constant number of k ≥ 1 uses of recourse in total, matching upper bounds for 1 ≤ k ≤ 3 , and a general upper bound for any value of k . For a variant where a constant number of k ≥ 1 uses of recourse can be used per step, we give tight bounds for all k ≥ 1 . We further look at a scenario where an algorithm is informed when the instance ends and give improved upper bounds in both variants for this case.

The time-optimal k-server problem minimizes the time spent instead of the distance traveled when serving n requests, appearing one after the other, with k servers in a metric space. The classical distance model was motivated by a hard disk with k heads. Instead of minimal head movements, the time model aims for optimal reading speeds. This paper provides a lower bound of 2k-1 on the competitive ratio of any deterministic online algorithm for the time-optimal k-server problem on a specifically designed metric space. This lower bound coincides with the best known upper bound on the competitive ratio for the classical k-server problem, achieved by the famous work function algorithm. We provide further lower bounds of k+1 for all Euclidean spaces and k for uniform metric spaces. Our most technical result, proven by applying Yao’s principle to a suitable instance distribution, is a lower bound of k+H_k-1 that holds even for randomized algorithms, which contrasts with the best known lower bound for the classical problem, which is polylogarithmic in k. We hope to initiate further intensive study of this natural problem.

Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you can travel to. When you are aware of all possible events and their costs at the beginning of the year, you can select the subset of the possible events that maximizes your happiness and is within your budget. On the other hand, if you are blind about the options, you will likely have a hard time when trying to decide if you want to register somewhere or not, and will likely regret decisions you made in the future. These scenarios can be modeled by knapsack variants, either by an offline or an online problem. However, both scenarios are somewhat unrealistic: Usually, you will not know the exact costs of each workshop at the beginning of the year. The online version, however, is too pessimistic, as you might already know which options there are and how much they cost roughly. At some point, you have to decide whether to register for some workshop, but then you are aware of the conference fee and the flight and hotel prices. We model this problem within the setting of online knapsack problems with estimates: in the beginning, you receive a list of potential items with their estimated size as well as the accuracy of the estimates. Then, the items are revealed one by one in an online fashion with their actual size, and you need to decide whether to take one or not. In this article, we show a best-possible algorithm for each estimate accuracy δ (i.e., when each actual item size can deviate by ± δ from the announced size) for both the simple knapsack (also known as subset sum problem) and the simple knapsack with removability.

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}$$ 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 · 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{))}$$