To Buy or Not to Buy: Online Rent-Or-Buy on Node-Weighted Graphs

We now formally present our results. We consider edge- and node-weighted graphs with $n$ vertices, denote by $\overline{n}$ the number of nodes with non-zero node-weight, and denote by $\tilde{k}$ the number of distinct terminals pairs arriving.

All our results are obtained through the same algorithmic framework, but using three different algorithms for prize-collecting set cover as a subroutine. We present the three resulting results separately.

We consider this to be our main result. All previously known deterministic algorithms use [5], and were a multiplicative factor of $O({\log }^{2}n)$ worse than the corresponding randomized version. This result closes this gap. We also note that it matches the currently best deterministic algorithm for the buy-only version (e.g. the special case $M=1$) from [10], and even slightly improves on it, as the dependency is now with respect to $\log \overline{n}$, instead of $\log n$.

The competitive ratio can be slightly improved to $O(\log \tilde{k}\log \overline{n})$, to depend on the number of distinct, actually arriving terminals pairs $\tilde{k}$, instead of the number of distinct terminal pairs $|T|$ that could arrive. However, to do so, it is necessary to rely on randomization, as already demonstrated in the corresponding lower bounds for online set cover in [2]. This again matches (and slightly improves) the corresponding result from [10] for the buy-only setting.

If one does not care about the logarithmic dependency on $\overline{n}$, it is possible to make this deterministic. The resulting competitive ratio is $O(\overline{n}\cdot \log \tilde{k})$, it depends linearly on the number of nodes with non-zero node-weights. This recovers the deterministic, $O(\log \tilde{k})$-competitive algorithm of [24] in the edge-weighted setting.

On a high-level, we combine the witness technique from the edge weighted variant for Rent-or-Buy from [24] with an instance of prize-collecting set cover. Before describing our approach, we briefly describe the approach for the edge-weighted setting, as well as the relevant techniques necessary for handling the node-weighted setting.

For the rent-or-buy setting, the difficulty lies in deciding whether it is worthwhile to buy an edge since we can reuse it at least $M$ times in the future, or whether we should rent. In the Ski Rental problem, e.g. Rent-or-Buy on a graph consisting of a single edge, a simple way to decide this and guarantee $2$-competitiveness is as follows: we rent $M$ times, then we buy. On a high level, this charging scheme was adapted to the edge-weighted Steiner problems in [24], surprisingly by a simple greedy procedure (though the analysis is quite involved!): if the new request $r$ lies close to $M$ previous requests for which we rented, buy the greedy path the algorithm selects for $r$. The cost of the bought path can be charged against these $M$ witnesses and all future requests close to any of them can be routed through the bought path. This ensures there cannot appear any clusters of $\mathrm{\Omega }(M)$ rented paths for which it would have been beneficial to just buy once, allowing for a charging scheme against the optimal solution.

Such a greedy approach cannot work in the node-weighted setting, even in the buy-only setting. Because the weights are on the nodes, it is possible for some vertex $v$ to be close to many (eventually) arriving terminals, but, all these terminals are quite far from each other. Indeed, this happens if these terminals have small distance to $v$, but $v$ has significant weight. Hence, even if we always buy a path for each arriving request, we might still end up with huge clusters of terminals for which an optimal offline solution only buys a single node. Hence, it is necessary to strategically buy certain nodes, which will decrease the distance of future requests. As shown in [23, 17], in the buy-only setting, these nodes can be selected through an instance of online non-metric facility location.

There are two main challenges to extend this to the rent-or-buy setting. First, analogous to the charging scheme for Ski-Rental problem, we need to balance the cost of renting and buying for every node and edge. Second, the number of requests is no longer bounded by the size of the graph: when we opt to rent, the same request can reappear again and incur an extra cost (unlike in the buy-only setting). Both of these issues cannot be handled by the charging scheme based on standard non-metric facility location. Our main contribution is to introduce a new charging scheme that instead relies on a prize-collecting variant of set cover, which itself is a special case of non-metric facility location. This extension to the prize-collecting variant takes care of these issues: It allows us to set up a charging scheme based on [24, 17], that ensures that no more than $M$ reappearances of terminals can “cluster”, balancing their cost against the cost of the prize-collecting instance of set cover, and naturally handling reappearances of terminals, with the competitive ratio only depending on the number of distinct terminals.

Finally, as a by-product of our conceptual simplification of using online (prize-collecting) set cover instead of (prize-collecting) non-metric facility location, our obtained bounds depend on $\overline{n}$, the number of nodes with non-zero node-weights, instead of $n$, the total number of vertices. This results in a framework that truly generalizes and recovers the best-known results from the edge-weighted setting, without incurring an extra $O(\log n)$ factor.

Most relevant to our work is the randomized procedure from [3]. This procedure can convert any algorithm for the buy-only setting into a randomized algorithm for the rent-or-buy setting with only a constant loss in the competitive ratio. It works in a very simple way: each request is passed to the buy-only algorithm with probability $1/M$, and for the remaining requests the algorithm rents. In their original paper, they only claim competitiveness against online adaptive adversaries when the algorithm for the buy-only setting is competitive against online adaptive adversaries. This would rule out using the $O(\log k\log n)$-competitive algorithm from [10], as that algorithm is not competitive against adaptive adversaries. However, a slightly more careful analysis of the result from [3] reveals that the same procedure can be applied, resulting in a randomized, $\mathrm{\Theta }(\log \tilde{k}\log n)$-competitive algorithm against oblivious adversaries. This is a weaker adversarial setting than that of an adaptive online adversary. We elaborate on this in the appendix of the full version.

We consider undirected graphs $G=(V,E)$ with a node-weight function $c:V\to {ℝ}_{\ge 0}$. This setting also captures edge-weights and is purely for convenience. For any pair of vertices $u,v\in V$, we set $d_G(u,v)$ to be the distance with respect to $c(\cdot )$ between $u$ and $v$, excluding the weights of $u$ and $v$. Given some set $A\subset V$, the subgraph induced by $A$ is denoted by $G[A]$, and consists of all vertices in $A$ as well as all edges from $E$ that have both endpoints in $A$. $G/A$ denotes the graph $G$ where the weight of all nodes in $A$ have been set to $0$, and $d_{G/A}(u,v)$ denotes the shortest distance between $u$ and $v$ in $G/A$, again excluding the weights of $u$ and $v$. Finally, given some radius $r>0$ and some vertex $u$, we define the open ball of radius $r$ around $u$ to be $B(u,r):=\{v\in V\mid d_G(u,v)+c_v\le r\}$, and its boundary to be . We set $\overline{B}(u,r):=B(u,r)\cup \mathrm{𝖻𝖽}B(u,r)$.

In the online node-weighted Steiner forest problem ($\mathrm{𝖭𝖶𝖲𝖥}$) in the rent-or-buy setting, we are given a node-weighted graph upfront, as well as a parameter $M$. Then, one-by-one, we receive pairs of terminals $(s_1,t_1),\mathrm{\dots },(s_k,t_k)\subseteq V\times V$. At each timestep $i\in [k]$, we need to maintain (augment) a set $B$ of bought nodes and select a set of nodes $R_i$ such that $(s_i,t_i)$ is connected in $G[B\cup R_i]$. The total cost is $M\cdot c(B)+{\sum }_{i\ge 1}^{k}c(R_i)$. The Steiner tree problem is defined analogous, except that we need to maintain a connected subgraph connecting all the arrived terminals $s_1,\mathrm{\dots },s_k$; this corresponds to the Steiner forest problem in the setting where the terminal pairs are of the form $(s_1,s_2),(s_1,s_3),\mathrm{\dots },(s_1,s_k)$.

An instance of the set cover problem ($\mathrm{𝖲𝖢}$) is given by a set system $(X,𝒮,\mathrm{𝖼𝗈𝗌𝗍})$, where $X$ is a groundset of elements, $𝒮\subseteq 2^X$ is a set of subsets of $X$, and $\mathrm{𝖼𝗈𝗌𝗍}:𝒮\to {ℝ}_{\ge 0}$ is a cost function. In the online setting, the elements are revealed one-by-one, and we need to ensure it is covered by a set. Sets from the cover cannot be removed, and the goal is to minimize the total cost of the selected sets. This problem has been studied in two settings. In the first, we have no knowledge of the set system. Only upon arrival of an element, we learn which sets contain it. In the second setting, we learn the set system $(X,𝒮)$ upfront. The subset of elements in $X$ that needs to be covered is revealed in an online fashion. Deterministic algorithms for online set cover are only meaningful in the second setting. In contrast, randomized algorithms against oblivious adversaries also apply in the first setting.

An online problem is a game between an online algorithm and an adversary. The adversary reveals the input $I_{\mathrm{𝖠𝖽𝗏}}$ to some problem piece by piece, after each reveal, the online algorithm must augment their current solution to maintain feasibility. The cost incurred by the online algorithm is compared to that of the adversary, its ratio is referred to as the competitive ratio. This notion does depend on the type of adversary, i.e. how the adversary is allowed to generate the sequence $I_{\mathrm{𝖠𝖽𝗏}}$ and how it has to service it. We give a brief description of three adversarial settings that we consider in this paper, as well as the corresponding notion of competitiveness. For a more detailed exposition, see [9].

All approaches for online set cover are based on the following general framework. Throughout the online phase, a monotonically increasing fractional solution is maintained, that is feasible for all arrived elements. In parallel, a rounding scheme is run to convert these fractional values to an actual integral solution, i.e. actually picking sets covering the arrived elements. For the first part, we rely on the following result.

Note that this fractional solution is compared to the best fractional solution in hindsight, and can be maintained deterministically. Hence this holds against an offline adversary in any adversarial model. In contrast, the rounding part does depend on the adversarial setting. Against an oblivious or semi-adaptive adversary, the rounding scheme is randomized and the guarantees hold in expectation. However, in contrast to the deterministic rounding scheme (against adaptive adversaries), the underlying set system does not need to be revealed upfront. We resume these results in the following two theorems.

Note that this generalizes the result for online set cover against oblivious adversaries. If the adversary is oblivious to the actions of the rounding procedure, their actions may as well be fixed. Hence, we may assume that $X^{\prime }=\widehat{X}$ and that the right-hand-side holds deterministically. In that case, combined with Theorem 4, this recovers the $O(\log k\log \mathrm{\ell })$-competitive ratio against (offline) oblivious adversaries of [11], where $k=|X^{\prime }|$ is the number of arriving elements. Against adaptive adversaries, we rely on the following.

We now give an online algorithm for the prize-collecting variant of online set cover.

We begin by describing an auxiliary instance of set cover $(X,\widehat{𝒮})$. For each reappearance of an element $e\in \tilde{X}$ with penalty $p$, there is an element $(e,p)\in X$. For each set $S\in 𝒮$, there is a set $\widehat{S}\in \widehat{𝒮}$ of same weight, so that $\widehat{S}$ contains all copies of the elements contained in $S$, i.e. $(e,p)\in \widehat{S}⟹e\in S$. Finally, for each element corresponding to $(e,p)\in \tilde{X}$, there is a singleton set ${\widehat{S}}_{(e,p)}$ of weight $p$ in $\widehat{𝒮}$. This construction is illustrated in Figure 1. Clearly, any integral (fractional) solution to this auxiliary instance corresponds to an integral (fractional) solution to the original instance of prize-collecting set cover of same cost and vice-versa.

We now describe our main algorithm for online prize-collecting set cover on instance $(\tilde{X},𝒮)$. We start by initializing an (empty) auxiliary instance $I_{\text{aux}}$ of online fractional set cover, $(X,\widehat{𝒮})$, for which we will maintain a monotonically increasing fractional solution ${\{x_{\widehat{S}}\}}_{\widehat{S}\in \widehat{𝒮}}$ by the algorithm of [12], see Theorem 4. We also initialize an instance $\tilde{I}$ of online set cover on the same set system as $(\tilde{X},𝒮)$. We will maintain monotonically increasing values ${\{x_S\}}_{S\in 𝒮}$, for which we will use a rounding scheme for online set cover such as [2, 11, 10] to decide which sets to select for $(\tilde{X},𝒮)$. Specifically, upon the arrival of an element $(e,p)\in \tilde{X}$, we pass a copy of the element to the auxiliary instance of set cover $(X,\widehat{𝒮})$ as detailed above, and we update our fractional solution. If the fractional value of the singleton set containing $(e,p)$ is at least $1/2$, i.e.

we pay the penalty. In parallel, we set $x_S=2\cdot x_{\widehat{S}}$, i.e. the fractional value of each set $S\in 𝒮$ is twice that of its corresponding set in $\widehat{𝒮}$. We add any sets that the rounding scheme on $(\tilde{X},𝒮)$ selects based on ${\{x_S\}}_{S\in 𝒮}$.

Our algorithm relies on an auxiliary instance of online prize-collecting set cover. We describe it in Algorithm 1.

In this section we prove Theorems 1, 2 and 3. To do so, we are going to show that the cost of Algorithm 1 can be charged against the optimum cost of the instance of prize-collecting set cover.

We will consider the if-case and the else-case separately. Let $C_{\mathrm{𝗂𝖿}}$ be the cost incurred in iterations that execute the if-case and $C_{\mathrm{𝖾𝗅𝗌𝖾}}$ be the cost incurred in the else-case. Let $C_{\mathrm{𝖲𝖢}}$ be the cost of the constructed solution to the prize-collecting set cover instance and let $C_{\mathrm{𝖲𝖢},\mathrm{𝗉𝖾𝗇}}$ and $C_{\mathrm{𝖲𝖢},\mathrm{𝗌𝖾𝗍𝗌}}$ be the penalty costs and the costs for the added sets in the solution, respectively. Note that $C_{\mathrm{𝖲𝖢}}=C_{\mathrm{𝖲𝖢},\mathrm{𝗉𝖾𝗇}}+C_{\mathrm{𝖲𝖢},\mathrm{𝗌𝖾𝗍𝗌}}$. We rely on the following four claims.