Online Algorithms for Set Packing with Renewable Capacities

We present a new variant of the set packing problem and show that a simple greedy algorithm is $O({\widehat{c}}_{\min }\cdot (D^{1/{\widehat{c}}_{\min }}-1))$-competitive for $D\ge 2$ and $3$-competitive if $D=1$, where ${\widehat{c}}_{\min }$ is the minimum capacity of the resources. Its proof is inspired by an analysis of a greedy algorithm for the unsplittable flow problem [23], but the new aspect here is that we are dealing with renewable resources, which significantly complicates the witness argument in the proof.

We then show that, for ${\widehat{c}}_{\min }=\mathrm{\Omega }(\log D)$, the greedy algorithm can be extended to an online algorithm with predictions whose competitive ratio is never worse than that of the original greedy approach and can, in fact, be reduced to a constant when the predictions are optimal. The key idea here is to compare the performance of an optimal algorithm with the performance of the greedy algorithm and an optimal algorithm that only have half of the capacity available in the resources, and whenever the capacity of a resource is renewed by an additive $c$ in the former case, it is only renewed by $c/2$ in the latter case. It turns out that the greedy algorithm still remains $O({\widehat{c}}_{\min }\cdot (D^{2/{\widehat{c}}_{\min }}-1))$-competitive in that case, and the optimal algorithm for half of the capacities still remains constant competitive if ${\widehat{c}}_{\min }=\mathrm{\Omega }(\log D)$. Combining these two insights then allows us to design an online algorithm with predictions that is $O(\log D)$-competitive for any predictions and constant competitive if the predictions are optimal, under the assumption that ${\widehat{c}}_{\min }=\mathrm{\Omega }(\log D)$.

Finally, we generalize the $D$-SPaRC problem in two meaningful ways, namely by addressing non-uniform request priorities and by handling requests with non-uniform weights. In fact, given a maximum priority of $p_{\max }$, a competitive ratio of $O({\widehat{c}}_{\min }\cdot (D^{\log (p_{\max }+1)/{\widehat{c}}_{\min }}-1))$ can be reached, and given a maximum weight of $\widehat{\mu }$, a competitive ratio of $O({\widehat{c}}_{\min }\cdot (D^{1/({\widehat{c}}_{\min }-\widehat{\mu })}-1))$ can be reached.

Set packing is a fundamental problem that belongs to Karp’s $21$ $𝒩𝒫$-complete problems [22]. Suppose that we are given a finite set $S$ and a collection $𝒞$ of subsets of $S$. Then, the (decision variant of the) set packing problem asks if there are $k$ pairwise disjoint subsets in $𝒞$. The set packing problem is not only $𝒩𝒫$-complete, but its optimization version has been shown to be as hard to approximate as the maximum clique problem by Hazan, Safra, and Schwartz [19], and the best known algorithm approximates it within a factor of $O(\sqrt{|S|})$ (see the work of Halldórsson, Kratochvíl, and Telle [18]). A more tractable problem is the $D$-set packing problem in which each set contains at most $D$ elements. When $D=1$, the problem is trivial, and when $D=2$, the problem is equivalent to finding a maximum cardinality matching, which can be solved in polynomial time. For any $D\ge 3$, the problem is $𝒩𝒫$-hard, as it is a generalization of the $D$-dimensional matching problem, and Karp [22] showed that $3$-dimensional matching is $𝒩𝒫$-hard. However, there are constant-factor approximation algorithms (e.g., Cygan [9], Fürer and Yu [15]).

$D$-set packing is equivalent to $D$-hypergraph matching where the sets of size at most $D$ correspond to hyperedges of size at most $D$. Online $D$-hypergraph matching has been studied by Tröbst and Udwani [30], where they show that any (randomized) online algorithm has competitive ratio at least $(2+o(1))/D$. (Note that they define competitive ratio inversely to the definition used in this paper, i.e., they consider the ratio of the algorithm performance to the optimal performance.) They also study the version of the problem where edges are allowed to be assigned fractionally. Notice that $D$-hypergraph matching differs from $D$-SPaRC in two ways: the hyperedges (sets) are disjoint and the nodes are not renewable.

A closely related problem to our formulation of the online $D$-set packing problem (without considering renewable capacities) is the online unsplittable flow problem (UFP), also referred to as the online unsplittable routing problem. In online UFP, we are given an undirected graph consisting of $n$ nodes and positive real-valued edge capacities. Each request comes in as a tuple of its associated source and destination nodes, along with a corresponding demand $d\in [0,1]$. The goal is to maximize the number of requests accepted. We can successfully satisfy a request if there exists a path in the graph such that each involved edge has sufficient capacity to satisfy the given demand $d$ (and the flow is never split amongst multiple paths). Once a request is accepted, the capacities along the chosen path will be updated accordingly. One can observe that online UFP, where each demand is exactly $1$, can be modeled using our formulation of online $D$-set packing, where each element is an edge, and each collection of elements represents a potential flow path to satisfy a given request. Furthermore, $D$ would be an upper bound on the length of any flow path in the graph. The online version of the UFP was first studied by Awerbuch, Azar, and Plotkin [2], who considered the case where the minimum edge capacity is $\mathrm{\Omega }(\log n)$ and designed an $O(\log n)$-competitive algorithm. Over the years, various works have continued to study the problem, aiming to improve the competitive ratio by leveraging different parameters (e.g., flow number by Kolman and Scheideler [23]) or different techniques (e.g., primal-dual technique by Buchbinder and Naor [8]).

Motivated by packet forwarding, Emek, Halldórsson, Mansour, Patt-Shamir, Radhakrishnan, and Rawitz [12, 13] introduced a formulation of the online set packing problem where initially we are aware of several subsets of $S$ whose elements are unknown, and elements arrive in an online manner, revealing which subset(s) they belong to. The goal is to irrevocably assign incoming elements to one of their potential subsets such that the total number of subsets with all elements assigned is maximized. For this formulation, they developed a randomized distributed algorithm to solve the problem and showed a nearly matching lower bound on the competitive ratio that holds even in the centralized setting. This version of the online set packing problem, where subsets are inputs and elements are requests, is a variant of $D$-SPaRC where the roles are reversed. Thus, solutions to $D$-SPaRC are not applicable to this formulation.

There is also some overlap between $D$-SPaRC and the online knapsack problem. In the online knapsack problem, a knapsack of some capacity receives elements one by one, each with a specific weight and value. An irrevocable decision to accept or reject the element is made, and the goal is to maximize the total value of the elements accepted to the knapsack without exceeding its capacity. One may notice that for the version of online knapsack where all elements have the same value but possibly different integer-value weights, this may be modeled as the non-uniform weight version of the $D$-SPaRC problem (see Section 4). The work of Marchetti-Spaccamela and Vercellis [29] was the first to study the online knapsack problem and showed that in the general case, there is no online algorithm that can achieve a non-trivial competitive ratio. The work of Zhou, Chakrabarty, and Lukose [32] subsequently studied this problem by assuming that the weight of each item is much smaller than the knapsack capacity and that the value-weight ratio of each item is lower and upper bounded by two constants $L$ and $U$, respectively. They were able to design an algorithm that solves the online knapsack with competitive ratio $\ln (U/L)+1$, which they showed to be optimal. There has been much subsequent research on the problem, and the interested reader may refer to the survey by Böckenhauer, Hromkovič, Komm, Rossmanith, and Stocker [5].

Another line of work related to $D$-SPaRC is augmenting online algorithms with replenishment, as done by Kang, Liu, and Udwani [21]. They introduce a black-box method that extends many existing online resource allocation algorithms (for resources with fixed capacities) to work with an arbitrary (adversarial or stochastic) replenishment process.

As mentioned earlier, drone routing can be modeled via the $D$-SPaRC problem. In particular, consider a graph where the vertices are windmills at which drone batteries can be stored/charged. Each node’s capacity represents the number of drone batteries that can be stored/charged at that node. The input is a sequence of delivery requests, where each request consists of a sequence of at most $D$ nodes to be traversed by a drone (to deliver a package from a starting point to an ending point). The goal is to satisfy the maximum number of requests, where a request is satisfied if each node in the assignment has non-zero capacity when the request is being serviced. Drone routing is a more recent variant of the vehicle routing problem, introduced by Dantzig and Ramser [11], a source of active research for the past 67 years. An excellent survey on various work that has been done in this area is that of Laporte [25]. Macrina, Di Puglia Pugliese, Guerriero, and Laporte [28] provide a wonderful survey of work focused on drone routing.

Many works have considered providing additional information to an online algorithm in order to improve its performance. One important model is the advice model, where an oracle has advance knowledge of the entire input, chooses to encode some information in a string of bits, and makes this string available to the algorithm throughout the runtime to aid in the computation. For more information on this advice model, please see the relevant section in Komm [24] and the survey by Boyar, Favrholdt, Kudahl, Larsen, and Mikkelsen [6]. Typically, the oracle is assumed to be correct. Learning-augmented algorithms, also known as algorithms with predictions, attempt to capture more realistic situations where the information, potentially generated by a machine learning algorithm, may not always be correct. In this model, introduced by Lykouris and Vassilvitskii [27], the prediction may or may not be correct. Algorithms are then designed to leverage correct predictions to achieve better performance while withstanding incorrect predictions, i.e., performing as well as if no prediction was available. To the best of our knowledge, there has been no prior attempt to study the set packing problem, let alone the $D$-SPaRC problem, in a learning-augmented model. However, in this setting, the knapsack problem has been studied [1, 3, 7, 10, 16, 17, 20, 26, 31].

It should be noted that there are many packing problems that may seem related to set packing, such as bin packing, but are, in fact, different and the solutions to these problems do not immediately apply to set packing.

Suppose that each request $r_i$ has a priority $p(r_i)\in \mathbb{N}$ and the goal is to maximize the sum of the priorities of the accepted requests. Furthermore, suppose that the maximum priority $p_{\max }$ is known in advance to the online algorithm and that ${\widehat{c}}_{\min }\ge \lceil \log (p_{\max }+1)\rceil$. Then we can use the following priority-based BGA algorithm: Use the standard trick of cutting the requests into $k=\lceil \log (p_{\max }+1)\rceil$ priority classes, where priority class $i\ge 0$ contains all priorities in the interval $[2^i,2^{i+1}-1)$, and reserve a $1/k$ fraction of the capacity of each node for each priority class. Moreover, capacity renewals are evenly distributed among the reserved capacities. Then it follows from Theorem 2:

Hence, if $D\ge 2$ and ${\widehat{c}}_{\min }\ge k\cdot \log D$ then the priority-based BGA is $O(k\cdot \log D)$-competitive.

Suppose that we allow the sets a request can choose from to be arbitrary non-empty multisets of $V$ of size at most $D$, where a node in $V$ can occur up to $\mu$ times in a multiset $S$, for some $\mu >1$. Note that in this case, $D\ge \mu >1$ as well, i.e., we do not have to consider the special case $D=1$. Then we can use the following weighted BGA algorithm: Given a request $r$, accept it whenever there is a feasible multiset $S\in r$ with $f(S)\le W$, and pick any such set in this case. A multiset $S$ is feasible if for every $v\in V$, $c(v)\ge \mu (v)$, where $\mu (v)$ is the number of times $v$ appears in $S$, and the weight $f(S)$ is defined as

where $f_v(x)=D^{x/\widehat{c}(v)}$ is defined as before. Then it follows: