{'fraction_non_alphanumeric': 0.040005745888098826, 'fraction_numerical': 0.010234863176039647, 'mean_word_length': 4.08713920350749, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improved Online Algorithm for Fractional Knapsack in the Random Order Model

The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting. However, the corresponding online setting has been handled only briefly in the theoretical computer science literature so far, although it appears in several applications. Even the previously best known guarantee for the competitive ratio was worse than the best known for the integral problem in the popular random order model. We show that there is an algorithm for the online fractional knapsack problem that admits a competitive ratio of 4.39. Our result significantly improves over the previously best known competitive ratio of 9.37 and surpasses the current best 6.65-competitive algorithm for the integral case. Moreover, our algorithm is deterministic in contrast to the randomized algorithms achieving the results mentioned above.


Introduction
The knapsack problem is well-studied and has a long history in the literature, both the offline and the online versions, where in the latter the items are revealed one after the other and an irrevocable decision whether to pick the current item has to be made immediately. In the online setting, one typically considers the random order model, in which the adversary controls the instance, i.e., the items with their weights and profits, but a permutation, chosen uniformly at random, determines the arrival order of the items. In this model, the performance measure of an algorithm A is its competitive ratio. We say that A is r-competitive with respect to the profit OPT(I) of an optimal offline algorithm for input I, if E[A(I)] ≥ (1/r − o(1)) · OPT(I) holds for all inputs I. Here, the expectation is taken over the random permutation as well as over random choices of the algorithm. The o(1)-term vanishes asymptotically with respect to the number of items in the input instance. In a series of papers [1,5,24], the competitive ratio for online knapsack has been improved to 6.65, achieved by a randomized algorithm in [1]. The online version of the fractional knapsack problem has not received much attention in literature as of yet. An application of the online fractional knapsack problem was introduced in [21], where the items are articles that are presented in a newsfeed to busy readers. The scarce resource is time and the profit is the information gain. Upon arrival of an article, readers see its length and a cue about the content. They can discard the article right away based on this information, or start reading it. They can read it completely or discard it at any time. The information gain is assumed to be proportional to the reading time and the cue about its content. Discarded articles are not considered again. Moreover, [21] contains a framework that turns any α-competitive algorithm for the online knapsack problem into an (α + e)-competitive algorithm for the online fractional knapsack problem. The approach is based on flipping a biased coin (w.r.t. α) and either executing the given algorithm or the famous secretary algorithm, where the first n/e items are discarded and then the first item that is better than the best item seen so far is chosen. Together with the result of [1], this led to the previously best known competitive ratio of 9.37 for the online fractional knapsack problem. In this paper, we cut the competitive ratio by more than half, namely to 4.39. To this end, we observed that the algorithm in [1] already contains a secretary algorithm on its own and that small and large items are treated separately due to the nature of the integral knapsack solution. Instead of treating it as a black box, relaxing the integrality constraints allows us to unify the small-item and large-item cases and output fractional values instead of binary ones, thereby achieving a better competitive ratio. Moreover, this also removes the randomization from the algorithm making it deterministic, and the expected value that determines the competitive ratio solely depends on the randomness of the input permutation.

Related Work
The study of the online (integral) knapsack problem was initiated by Marchetti-Spaccamela and Vercellis [28], who showed that there is no constant-competitive deterministic online algorithm. Moreover, Chakrabarty et al. [34] extended the same hardness result to randomized algorithms. Motivated by the difficulty of the adversarial model for this problem, a number of beyond worst-case scenarios have been investigated. The most popular of these is the random order model that has received increasing attention in the field of online algorithms. In this model, the online knapsack problem was first studied by [5], showing a 10e-competitive algorithm. Kesselheim et al. [24] developed an 8.06-competitive randomized algorithm for the generalized assignment problem, which generalizes to a setting with multiple knapsacks of different capacities. Albers et al. [1] achieved the currently best known upper bound of 6.65. The online fractional variant under adversarial arrivals was first considered in [30]. There, the knapsack capacity is augmented by a factor 1 ≤ R ≤ 2, and the algorithm can remove previously packed items. The plain version of the fractional knapsack problem in the random order model was studied in [21], presenting a 9.37-competitive randomized algorithm, which we improve upon. Recently, [31] considered a general version of the fractional online knapsack problem with multiple knapsacks and rate constraints. A further branch of research considers the infinitesimal assumption (or that the packing is allowed to be fractional), i.e., the profit of a single item is small compared to the profit of the optimal integral solution, under which Vaze [33] gave a 2e-competitive algorithm. In addition, a common approach combined with the infinitesimal assumption is to assume that the density (profit-size ratio) of each item is in a known range [8,9,34]. Another problem closely related to the random order model is the secretary problem [14,26], that is, a special case of the online knapsack problem in which the weights are uniform and equal to the weight constraint. One natural generalization of the latter is the k-secretary problem [2,11,25], where k elements need to be selected, as well as the matroid secretary problem [6,15], where elements of a weighted matroid arrive in random order, and in both of these, the goal is to maximize the combined value of the selected elements. Other variants of online knapsack presented in the literature include removable models, where removals can incur no cost or a cancellation cost [3,4,17,18,20], reservation costs [7], an expected capacity constraint [32], and resource buffering [19]. Furthermore, there have been alternative approaches to the random order model, such as stochastic versions of the online knapsack problem [12,13,16,27,29], a random order model with bursts of adversarial time steps [22], and the the advice complexity model [10].

Our Contribution
Theorem 1. There exists a 4.39-competitive deterministic algorithm for the online fractional knapsack problem in the random order model. We achieve this result by analyzing a natural variation of the algorithm from [1]. As in the original version for the online knapsack problem, the algorithm works in three phases -the sampling phase, the secretary phase, and the knapsack phase. The transition between the phases happens at iterations ⌊cn⌋ and ⌊dn⌋, respectively, where 0 < c ≤ d ≤ 1 are optimized to achieve the best possible competitive ratio when combining our analyses of the second and third phase contributions. The algorithm can be considered as a blending of two algorithms that share the first phase, which is possible because no items are picked in the sampling phase; thus, there is no interference between both algorithms. After the first phase, i.e., after roughly 47.5% of all items, the secretary algorithm takes over and exclusively decides the items of the second phase. It does so by selecting all items that have a larger profit than the most profitable item seen in the sampling phase. Should picking the current item exceed the knapsack capacity, the item is picked to the largest extent possible to fill the knapsack. If there is still capacity left after the second phase, i.e., after roughly 60.1% of all items, we switch from the secretary to the knapsack algorithm, which then exclusively fills in a fraction of each arriving item according to the optimal (fractional) solution of all items revealed so far and the remaining capacity. It is interesting to note that we do not distinguish between large and small items in our analysis, in comparison to [1]. Furthermore, in the analysis of the secretary algorithm, we only account for the probability of picking the item that has the largest contribution to the objective value of the optimal (fractional) solution. This is sufficient to cover the case where the optimal solution consists of a single item, a situation that the knapsack algorithm (or our analysis of it) cannot handle well. In fact, if we forced c = d in the parameter optimization, we could not get a better competitive ratio than 6.63, which is still better than the competitive ratio from [21], but significantly worse than the best ratio from this paper. On the other hand, if we did not use the knapsack algorithm at all (d = 1), we obtained the well-known secretary algorithm, where the sampling phase ends after skipping a c = 1/e fraction of all items (justifying the naming).

Preliminaries
Definition 2 (OFKP). We are given a set I of n items, each item i ∈ I has size s i ∈ Q >0 and a profit (value) v i ∈ Q ≥0 . The goal is to find a maximum profit fractional packing into a knapsack of size W ∈ Q >0 , i.e., a solution x ∈ Q n ≥0 s.t. i∈I s i x i ≤ W and i∈I v i x i is maximized. The items are revealed one by one in a round-wise fashion. In round ℓ ∈ [n], the algorithm sees item ℓ with its size and profit. It has to decide immediately and irrevocably the fraction x ℓ of the current item in the final packing.
We make the following two assumptions without loss of generality: (i) No item has size larger than the knapsack capacity 1 , (ii) Items have distinct values 2 . Using assumption (ii), we obtain that there is a unique (optimum) solution x * for the given set of items I. In fact, profit-to-weight ratio ties can be broken by taking the most valuable element which is unique by assumption (ii).
Next, we formalize the optimal (fractional) solution for a given subset Q ⊆ I. Let the density of an item be the ratio of its profit to its size. The optimal (fractional) solution has a clear structure: There exists a density threshold ρ Q such that any item i Meaning that the k − 1 densest items are packed integrally and the remaining space is filled by the maximum feasible fraction of the k-th densest item. Let I(ℓ) denote the subset of items I revealed up to round ℓ and define x (ℓ) to be the optimal (fractional) solution for the item set I(ℓ). Let OPT be the total profit of the optimal (fractional) solution x * for the item set I, i.e., OPT = i∈I v i x * i . For convenience of notation, let OPT also denote the set of items that are part of the optimal (fractional) solution, i.e., each item i whose x * i > 0, and let K be its cardinality. Additionally, we label items in descending order of contribution to OPT such that As in [1], we will use the following well-known fact to obtain lower or upper bounds on sums in closed form.
Fact 3. Let f be a non-negative real-valued function and let a, b ∈ Z.

Review of the Blended Approach
A standard approach used by packing algorithms in the online setting is the following. Algorithms have a sampling phase, during which all items are rejected, and a decision phase, where items may be accepted according to some decision rule developed according to the information gathered in the sampling phase. The novel idea presented in [1] is to combine two algorithms, A 1 and A 2 , in a blended manner. The strategy is to make a better use of the entire instance by letting the two algorithms have a common sampling phase, and, subsequently, using the sampling phase of one algorithm as the decision phase of the other. Let 0 < c ≤ d ≤ 1 denote some constant parameters to be specified later. Rounds 1, . . . , ⌊cn⌋ define the common sampling phase. For rounds ⌊cn⌋ + 1, . . . , ⌊dn⌋, there is the A 1 decision phase, while, A 2 continues its sampling phase. From round ⌊dn⌋ + 1 the algorithm A 1 stops and the A 2 decision phase starts until the end of the stream. As in [1], we make the assumption cn, dn ∈ N for the analysis, which does not affect the competitive ratio substantially for n large enough. Clearly, combining the two algorithms without an initial random choice on whether to run A 1 or A 2 ( [5,21,24]) comes at the cost of possibly having a non-empty knapsack when A 2 starts its decision phase, thus, deteriorating A 2 performance. However, we will see that with some sufficiently high probability the algorithm A 1 does not pack any item.
In the online integral knapsack algorithm developed in [1], the algorithm A L deals with all items that consume more than 1/3 of the knapsack capacity. Items whose size is at most 1/3 of the knapsack capacity are packed by algorithm A S . The algorithm A L exploits the connection with the 2-secretary problem because at most two large items can fit in the knapsack. The algorithm A S packs the current small item integrally with probability equal to its value in the optimal fractional solution formed by the items occurred so far. One possible reason for which A L and A S operate on different instances, i.e., the instances that consist of large and small items respectively, is that the optimal integral solution is not monotone. Namely, in the optimal integral solutions for the items seen until rounds ℓ, m for ℓ < m denoted by x (ℓ) and x (m) respectively, there might be an item i such that x Notably, this comes at the cost of not packing large items using A S , as the large items in the optimal integral solution that algorithm A L considers may be arbitrarily different from the large items in the optimal fractional solution that A S considers.

Application of the Blended Approach in the Fractional Case
In the fractional variant of the problem, we can overcome the limitation described above. The fractional relaxation allows us to make both algorithms sharing the same instance of the problem. The secretary algorithm A S packs the most profitable items, whereas, the knapsack algorithm A K packs both small and large items (fractionally when needed) that are part of the optimal fractional solution OPT. In the analysis of A S , the connection between the fractional knapsack problem and the k-secretary problem can be extended beyond the 2-secretary problem, unlike the integral case, losing only the symmetry property of packing an item before another when there is an item taken fractionally in the optimal (fractional) solution. However, we will see that the connection with the 1-secretary problem is enough for our purpose. Next, we give give a high-level description of the proof of Theorem 1 using Algorithm 1.
Proof. Let A be the algorithm obtained by combining A S and A K . Moreover, define p i , q i to be some probabilities that we introduce later. By setting parameters c, d to 0.47521, 0.60138,

Algorithm 1: Online Fractional Knapsack A
Input : permutation π of item set I, knapsack capacity W , parameters c, d ∈ (0, 1] with c ≤ d. Item i appears in round π(i) and reveals v i and s i . Output: feasible fractional knapsack packing, i.e., 0 ≤ x i ≤ 1 for item i ∈ [n].
Let ℓ be the current round and i be the online item of round ℓ; Let v * be the maximum profit seen up to round ⌊cn⌋; for round ℓ ∈ {⌊dn⌋ + 1, . . . , n} do ⊲ Algorithm A K x (ℓ) := optimal fractional knapsack packing on I(ℓ); In the remainder of this paper, we analyze the performance of A S and A K . The algorithm A S and its analysis are similar to the algorithm A L and its analysis in [1] based on the singleref algorithm [2] for the k-secretary problem. The algorithm A K and its analysis extend the approach of [1] to consider the possibility of packing items fractionally. Namely, we make A K taking the largest possible fraction of an item that is part of the optimal fractional solution seen at round ℓ according to the available knapsack capacity. The resulting competitive ratio obtained by combining lower bounds on the expected profit of algorithms A S and A K is analyzed in Section 5.

Secretary Algorithm A S
The following is an adaptation of single-ref developed for the k-secretary problem in [2] and applied to the knapsack setting in [1]. There is a useful connection between the online knapsack problem under random arrival order and the k-secretary problem. The latter is defined as an unweighted version of online knapsack in the random order model, or equivalently, items can be seen as W/k large. In contrast, in our problem items may be larger than W/k.
Algorithm. The algorithm A S works as follows. During the initial sampling phase of ⌊cn⌋ rounds, the algorithm rejects all items and identifies as best sample the encountered element with the highest value. In rounds ℓ ∈ {⌊cn⌋ + 1, . . . , ⌊dn⌋}, the algorithm takes the the largest possible fraction (according to the remaining knapsack capacity) of the items whose individual profit beats the profit of the best sample. Consequently, the first item beating the best sample will be taken integrally. Then, the algorithm maximizes the fraction of each subsequently accepted item.
Analysis. Let p i for i ∈ [n] be the probability that A S packs the i-th most profitable item as the first element. When considering the probability p i , we do not specify what the algorithm will further do, i.e., after the first accepted item, any or no second item may be included and so on for subsequent items. In the following, we report the lower bounds for the probabilities p i showed in [1]. Note that these lower bounds do not depend on the integral or fractional variant considered as the first item can be always packed integrally. Let us define a permutation σ :

Lemma 4 ([1]).
We have the following lower bounds for the probability p i that item σ(i), i ∈ [n], is accepted by A S as the first item By the lemma above, we have p(1) = c ln d c for i = 1. Furthermore, the value of OPT is upper bounded by the sum of the profits of the K most profitable items because items are sorted in decreasing order of contribution to OPT, thus, v σ(i) ≥ v i x * i . This yields concluding the analysis of algorithm A S .

Knapsack Algorithm A K
In this section, we present the algorithm A K that leverages the structure of optimal fractional solutions restricted to the items seen so far. In contrast to the small-item algorithm developed in [1], which uses the optimal fractional solutions to obtain an integral packing via randomized rounding, our deterministic algorithm uses the value of the current item in the fractional solution to the extent of the remaining knapsack capacity.
Algorithm. The algorithm A K works as follows. During the initial sampling phase of ⌊dn⌋ rounds, the algorithm rejects all items. In each round ℓ ≥ ⌊dn⌋+1, the algorithm computes an optimal fractional solution x (ℓ) for I(ℓ). We pack an x (ℓ) i fraction of the current item if there is enough space, otherwise we pick the largest possible fraction according to the remaining space. Thus, the algorithm determines the fraction of item i, denoted by x i , as follows Analysis. We study the performance of algorithm A K assuming it has the entire knapsack at its disposal, i.e., a capacity of W , and afterwards show how this occurs with constant probability. In our proofs, we consider an arbitrary fixed element i ∈ OPT and define δ ∈ (0, 1] to be a parameter representing the fraction of the knapsack capacity W that element i occupies in our online solution. For a fixed δ, the proofs of Lemma 5 and Lemma 6 almost immediately follow from the small-item case analysis in [1]; we reproduce their proofs for completeness and include few changes in Lemma 5 that have to be made in order to adapt them to our fractional setting. In the second part of the analysis, in Lemma 7, we make use of δ to exploit the possibility of packing items fractionally.

Lemma 5 ([1]
). Let i ∈ OPT and x i (ℓ) be the fraction of item i that is packed by A K in round ℓ. For ℓ ≥ dn + 1, it holds that Proof. In a random permutation item i arrives in round ℓ with probability 1/n. In round ℓ ≥ dn + 1, the algorithm packs i for an x (ℓ) i fraction provided that there is enough space. Note that the rank w.r.t. profit-to-weight ratio of item i in I(ℓ) is less than or equal to its rank in I. According to the structure of the optimal fractional solutions, this implies that x Moreover, if the current resource consumption X is at most (1 − δ)W , then the current item i can be packed up to a fraction δW/s i . By treating x * i as a parameter, it is not required to analyze the resource consumption in each round in expectation over all items. The latter approach appears in [23], which relies on the fact that in any step k of the algorithm the choice of the random permutation up to this point can be modeled as a sequence of independent random experiments. Let X k be the resource consumption in round k < ℓ. By assumption, the knapsack is empty after round dn, thus X = ℓ−1 k=dn+1 X k . Let Q be the set of k visible items in round k. The set Q can be seen as uniformly drawn from all k-item subsets and any item j ∈ Q is the current item of round k with probability 1/k. The algorithm packs any item j for at most an x (k) j fraction, thus where the last inequality holds because x (k) is a feasible solution for the knapsack of size W . By linearity of expectation and the previous inequality, the expected resource consumption up to round ℓ is Applying Markov's inequality yields In the next Lemma, we use Lemma 5 to lower bound the total probability that a fixed fraction of a specific item will be packed.
Lemma 6 ([1]). Let i ∈ OPT and x i be the fraction of item i that is packed by A K . It holds that Proof. Summing up the probabilities from Lemma 5 over all rounds ℓ ≥ dn + 1 gives The last inequality follows from n ℓ=dn+1 ln ℓ dn = n−1 ℓ=dn ln ℓ dn + ln 1 d and, by Fact 3, n−1 ℓ=dn ln ℓ dn ≤ n dn ln ℓ dn dℓ, which evaluates to n · d − 1 + ln 1 d . The claim follows by rearranging terms.
Observe that the above lower bound on the probability becomes negative for any δ ≥ 2 + ln(d)/(1 − d). Therefore, it is only safe to use it for those items i that have a utilization where the utilization of an item measures its space consumption in the optimal fractional solution w.r.t. the total capacity andμ denotes the maximum utilization allowed by our lower bound. In the following Lemma, we compute a lower bound on the expected profit obtained packing item i ∈ OPT using A K , crucially relying on the ability of packing items fractionally.
Lemma 7. Let i ∈ OPT and E i [A K ] = q i · v i x * i be the expected profit obtained by A K from the fraction of item i that is packed in the optimal (offline) fractional solution. We have Proof. Our goal is to compute the expected profit obtained from item i ∈ OPT by summing up the lower bounds on the probability that item i is packed for a fraction x i ∈ (0, x * i ]. To this end, let N be an arbitrarily large parameter. We define δ j = 1 − j/N for all j ∈ {0, . . . , N }. It follows that δ j > δ j−1 . We may choose N appropriately such that there is an index k ∈ {0, . . . , N − 1} with δ k = µ i . Note that µ i is a rational number since the input data is rational. Let us define m j = δ j W s i for j ∈ {k, . . . , N }. Recall that we consider a discrete probability space over the permutations of [n]. We consider the discrete random variable X i for the fraction of item i that is selected by A K . Let Ω i denote the finite set of values that X i can attain. We have We rearrange the sum as follows By definition, we have δ j − δ j+1 = 1/N , δ N = 0, and δ k = µ i . This implies that for any integer k ′ ≥ k, which we will choose as the smallest index such that the lower bounds from Lemma 6 are positive, i.e., k ′ := max k, N · d−1−ln d It is easy to check that 1 − d − ln 1 d − 1 n ln 1 d ≤ 0 for d ∈ (0, 1]. Thus, using Fact 3, we deduce By plugging in the above upper bound and observing that δ k ′ = 1 − k ′ /N , we obtain Note that 1 n ln 1 d = o(1) and that we can achieve ln for any ε > 0, which yields the desired lower bound for µ i = δ k <μ. Moreover, if k ′ = N · d−1−ln d 1−d , we can obtainμ − ε ≤ δ k ′ ≤μ for any ε > 0, which completes the proof.
This establishes the profit obtained by items in OPT using A K . However, algorithm A can only benefit from A K if algorithm A S has not filled the knapsack completely. As we do not have any control over the (expected) size of the items packed by A S , we now condition on the event that it starts with an empty knapsack: . With a probability of at least c/d, no item is packed by A S .
Let ξ denote the event of an empty knapsack after round dn. The following Lemma bounds the overall expected profit from A K 's packing for algorithm A by applying Lemma 8.
Proof. By Lemma 8, the probability of an empty knapsack after round dn is at least c/d. Thus, we obtain by linearity of expectation and Lemma 7.

Competitive Ratio Analysis
We provide a unified analysis of the competitive ratio achieved by algorithm A which combines A S and A K . We determine the best choice for the parameters c and d w.r.t. the bounds that we have proven before. Note that our bounds only make sense for 0 < c ≤ d ≤ 1 andμ > 0. The latter yields an additional lower bound on d, which is the smaller of the two roots of 2− 2d+ ln d, say, d min ≈ 0.20319. In the following, we only consider the expected contribution by items that are contained in OPT. That is, Our strategy is as follows. We first reason about adversarial instances. We use these to determine the parameters c and d that yield the best competitive ratio that is permitted by the analysis of A S and A K above. Afterwards, we formally prove that we indeed covered the worst-case, i.e., we achieve the postulated competitive ratio with the particular values for c and d on all instances. We have to take care of the following two situations: (i) OPT only contains a single item.
(ii) OPT contains many items with a small utilization.
In the former case, we have that OPT must contain the most profitable item, which the secretary algorithm packs with a probability of p 1 . Moreover, we start A K with an empty knapsack with probability of at least c/d and pack the most profitable item there with a probability of q 1 ≥ q(1). Hence, we obtain Proof. By Lemmas 4 and 9, the profit obtained by items in OPT is at least i∈OPT p(i) + c d q(µ i ) · v i x * i . Clearly, the case K = 1 follows from the above optimization problem. For the general case K ≥ 2, the minimum coefficient over all terms in the summation, for the given c and d, may be smaller than the desired competitive ratio. However, if their average is larger than z, then we can exploit this as follows. The idea is that we transport excess from items with a smaller index (i.e., larger contribution to OPT), to items with larger index that may have a deficit. That is, we can redistribute the excess at item 1 to any larger indexed item. Note also that for any µ i , it holds that c/d · q(µ i ) ≤ z and that we can assume without loss of generality that µ 1 ≥ . . . ≥ µ K as any other assignment of the µ i 's would give an higher expected value. Therefore, we deduce the following sufficient condition for our lemma