Vantage Point Selection Algorithms for Bottleneck Capacity Estimation

In this setting, we work with the assumption that the ordering of the edge capacities is uniformly randomly chosen from a permutation of $1,2,\mathrm{\dots },m=|E|$. Thus, each edge has equal chance of being the one with the smallest capacity among all edges in the network. Here we consider algorithms in a non-adaptive manner, where the $k$ vantage points are selected all at once and probes are issued afterwards. We seek to maximize the expected number of edges revealed.

In the adaptive setting, we work in the worst-case model where we assume the edge capacities to be arbitrarily fixed distinct real numbers, unknown to the algorithm. We also allow algorithms that run in an adaptive manner, where the vantage points are selected one by one, with probes from a vantage point issued immediately upon selection, before we select the next vantage point.

Here we aim to perform well on any specific input. In other words, we study the instance-optimal setting. Traditionally, instance optimality is studied by comparing the output of an algorithm to the optimal solution for the input instance. In this spirit, we assume an algorithm $OPT$ that is already aware of all the capacities, and for a specific input instance $I$, let $OPT(I)$ denote the maximum number of edges revealed by $k$ vantage points on instance $I$, i.e., obtained by enumerating all subsets of $k$ vantage points and keeping the best choice. In contrast, a capacity-unaware algorithm will be called $(\alpha ,\beta )$-instance optimal if after selecting at most $\alpha k$ vantage points (possibly in an adaptive manner) on the input instance $I$, it can reveal at least $OPT(I)/\beta$ many edge capacities. We can think of $\alpha \ge 1$ as the resource augmentation factor and $\beta \ge 1$ as the approximation factor for the objective function.

We close this subsection with the following observations on the problem.

We start with the nonadaptive setting with stochastic capacity assumption, where $k$ vantage points are selected before any information on the bottleneck capacities is revealed. Here, the ordering of the capacities $c$ is assumed to be a random permutation of $[m]$, and we look for an algorithm that maximizes the expected performance. This problem is NP-hard, since the vertex cover problem is a special case. We therefore aim for approximation algorithms and compare with the optimal algorithm which works under the same assumption.

A first observation is that the expected number of revealed edges obtained using a subset $S$ of vantage points is a monotone and submodular function with respect to $S$. That is, adding a new vantage point $w$ is always beneficial and adding $w$ to a set $Y$ rather than $X$, with $X\subseteq Y$, has a diminishing return. This observation allows us to use a greedy algorithm to select the next vantage point that maximizes the expected marginal increase of the objective function, which yields a $(1-1/e)$-approximation algorithm, by known results for maximizing coverage for submodular functions [26]. To obtain our approximation result, then, we must address the non-trivial calculation of the expected marginal increase of adding a vantage point to the set being constructed greedily. A crucial step here is to efficiently count the number of capacity assignments to the graph such that an edge $e$ is revealed as the result of a new vantage point. We show that the algorithm can be implemented in time $\tilde{O}(km{n}^3)$, with $n$ as the number of vertices, $m$ as the number of edges and $k$ as the total number of vantage points selected.

We remark that one can also resort to a sampling-based approach (e.g., see Proposition 3 in [23]), which does not provide better running time in general and can only provide an approximate solution which leads to a $1-1/e-\epsilon$ approximation factor. Our deterministic algorithm provides more insight into the structure of the problem.

In the adaptive setting, we prove the following results. First, we show interesting lower bounds for the tradeoffs of parameters $\alpha ,\beta$ and $k$ for $(\alpha ,\beta )$-instance optimal algorithms, where $OPT$ selects $k$ vantage points (with the full knowledge of capacities). One trivial algorithm is to select all $n$ vertices as vantage points, as opposed to the $k$ vertices selected by $OPT$, obtaining $\alpha =n/k$ and $\beta =1$. We thus ask if we can lower $\alpha$ with respect to the other parameters. Our lower bounds suggest that $\alpha$ cannot be too small. For deterministic adaptive algorithms, we show that ${\alpha }^2\beta =\mathrm{\Omega }(n/k)$; for randomized adaptive ones, $\alpha \beta =\tilde{\mathrm{\Omega }}(\sqrt{n/k})$. These lower bounds apply for algorithms that can perform any finite computation between the selection of the $k$ vintage points.

We then show that both bounds are tight when the underlying graph is a tree, i.e., we give vantage point selection algorithm achieving the same tradeoffs. For planar graphs, we give a deterministic algorithm that achieves a tradeoff of $\alpha \beta =O({(n/k)}^{2/3})$. Finally, while we leave open the question of existence of an $\alpha \beta =o(n)$ algorithm for general graphs, we show that if the shortest path trees are not unique, and each shortest path tree may break ties independent from others, there is a stronger lower bound of $\alpha \beta =\mathrm{\Omega }(n^{1-\epsilon })$, for all $\epsilon >0$.

We present the algorithmic results in the main body of the paper. We postpone the hardness proof for both settings and some proof details to the Appendix.

We will assume $k$ divides $n$ for simplicity. Let $G$ be the graph with $k$ connected components $P_i$, $1\le i\le k$, where each $P_i$ is a path on $n/k$ vertices. Let $𝒜$ be a deterministic and adaptive algorithm. Consider the following adversarial strategy. For any $P_i$, whenever $𝒜$ selects a vantage point $v_0^i$ that is the first vantage point on $P_i$, the adversary reveals only the two neighboring edges on $v$, giving them the lowest two capacities out of the $n/k-1$ edges in $P_i$. At any point in the execution of $𝒜$, let $\{v_0^i,\mathrm{\cdots },v_{j-1}^i\}$ be the vantage points selected on $P_i$ so far, and assume $𝒜$ selects a new vantage point $v_j^i$ on $P_i$. If $v_j^i$ is not a neighbor of $v_k^i$ for any $1\le k\le j-1$, the adversary reveals the two edges incident to $v_j^i$, giving them the next lowest capacities of all the edges revealed in $P_i$ so far. Otherwise, the adversary reveals either one or zero edges (depending on whether one or both neighbors of $v_j^i$ was already selected). We observe that the adversary’s strategy is consistent: for any $P_i$, all edges yet to be revealed have a higher capacity than those revealed.

Let ${\lambda }_i$ be the number of vantage points selected on $P_i$ at the end of $𝒜$. We have that ${\sum }_{i=1}^k{\lambda }_i=\alpha k$, where $\alpha$ is the resource augmentation factor. The adversary now reveals the remaining edges in the following way. Fix a path $P_i$. If ${\lambda }_i=0$, the adversary gives all edges in $P_i$ decreasing capacities from the first vertex in $P_i$ (and therefore selecting that vertex would have revealed all $n/k-1$ edges). Otherwise, if ${\lambda }_i>0$, there is a contiguous set of ${\mathrm{\ell }}_i=(n/k-1)/({\lambda }_i+1)-2$ edges such that none of the endpoints have been selected by $𝒜$ as vantage points. The adversary gives them decreasing weights, starting from, say, the first vertex in this set of edges. Selecting this first vertex would have revealed not only the ${\mathrm{\ell }}_i$ edges with decreasing capacities, but also the two “outer edges”, since their capacities are lower. Thus selecting this vertex reveals ${\mathrm{\ell }}_i+2=(n/k-1)/({\lambda }_i+1)$ edge capacities. We now have that $OPT\ge {\sum }_{i=1}^k({\mathrm{\ell }}_i+2)$.

Clearly $𝒜$ reveals at most $2\alpha k$ edges, at most two per vantage point selected. Thus

The second equation implies that there exists a set $S\subset \{1,\mathrm{\cdots },k\}$ such that $|S|=k/2$ and ${\lambda }_j\le 2\alpha$ for all $j\in S$. We will use $S$ to lower bound the sum in the first inequality. We have

and thus ${\alpha }^2\beta \ge n/24k$, proving the theorem. $◀$

Next, we consider a randomized algorithm $𝒜$ that selects at most $\alpha k$ vantage points. Given an instance $G=(V,E,w,c)$, different runs of $𝒜$ may reveal different numbers of edge capacities. We define $\beta$ for a randomized algorithm to be OPT divided by the expected number of edge capacities revealed by $𝒜$ over all runs of $𝒜$ on $G$ (expectation over random coins of $𝒜$). The proof of the following theorem can be found in Appendix C.

Both claims will require the notion of a “cover” $S$, which we describe first. We take the tree $T(r)$ rooted at an arbitrary vertex $r$. Take the lowest vertex $v$ with at least $\sqrt{n}$ descendants with $v$ inclusive (i.e., any child of $v$ has fewer than $\sqrt{n}$ descendants). We put $v$ in set $S$. We remove $v$ and its descendants and repeat until we are left with at most $\sqrt{n}$ vertices. Clearly there are at most $\sqrt{n}$ vertices in $S$. We call this set $S$ a cover of the tree. Sometimes we will need to vary the number of descendants: we will denote by $S(\gamma )$ the cover of size at most $n/\gamma$, generated in the same way as above starting with the lowest vertex $v$ with at least $\gamma$ descendants. The covers satisfy the following lemma.

$S(\gamma )$ satisfies the requirement for the root $r$ chosen during the construction of $S(\gamma )$ by design. Now suppose we have a different root $r^{\prime }\ne r$. We argue that $S(\gamma )$ again covers all but $\gamma$ vertices in the descendants of $S(\gamma )$ for $T(r^{\prime })$ rooted at $r^{\prime }$. Consider the tree $T(r)$ rooted at $r$. We run a case study.

If $r^{\prime }$ is not a descendant of any vertex $v$ in $S(\gamma )$, then all descendants of $S(\gamma )$ in $T(r)$ remain to be descendants of $S(\gamma )$ in tree $T(r^{\prime })$. Thus we are done.

If $r^{\prime }$ is a descendant of a vertex $v$ in $S(\gamma )$. Wlog we take $v$ as the lowest such ancestor of $r^{\prime }$. We take the child $v^{\prime }$ of $v$ who is the ancestor of $r^{\prime }$ (or $r^{\prime }$ itself). All vertices that are not in the subtree of $v^{\prime }$ are now descendants of $v$ in $T(r^{\prime })$. Thus they are “covered”. Now we focus on the vertices in the subtree of $v^{\prime }$ in $T(r)$. Among these vertices, those that are descendants of some other vertex $w$ of $S(\gamma )$ in this subtree will continue to be descendant of $w$ in $T(r^{\prime })$ – since $r^{\prime }$ is not in the subtree with root $w$. Thus the only vertices left would be those that are not in subtree of other vertices in $S(\gamma )$. There can only be at most $\gamma -1$ vertices – otherwise $v^{\prime }$ would have been selected to $S(\gamma )$ in the computation of $S(\gamma )$. $◀$

The algorithm $𝒜$ selects a cover, with any $r\in T$ as the root in the above cover-selection procedure and $\gamma =n/(\alpha k)$. Thus the size of the cover is at most $\alpha k$. If the size of the cover is strictly smaller than $\alpha k$, we select some arbitrary vantage points to make the total number of selected vantage points equal to $\alpha k$.

Let $m$ be the total number of edge capacities revealed by $OPT$. Consider a vertex $r^{\prime }$ chosen by the OPT solution. By Lemma 15, in the tree rooted at $r^{\prime }$, all but $\gamma$ vertices of $T$ are descendants of $S(\gamma )$. Thus all the edges that are revealed by $r^{\prime }$ in the OPT solution, except those that are not descendants of $S(\gamma )$, will be revealed as well by our algorithm $𝒜$. Since OPT chooses $k$ vantage points, algorithm $𝒜$ would only miss at most $k\gamma$ edges and thus reveal at least $m-k\gamma$ edges.

Now we do a case analysis. If $m\ge 2k\gamma$, $m-k\gamma \ge m/2$. Thus $\beta \le m/(m-k\gamma )\le 2$. ${\alpha }^2\beta \le n/k$, since $1\le \alpha \le \sqrt{n/k}$. On the other hand, if $m\le 2k\gamma$, algorithm $𝒜$ selects $\alpha k$ vantage points, just the edges incident to these points reveal at least $\alpha k/2$ many edge capacities (in the worst case, these vertices form a matching). Therefore $\beta \le \frac{m}{\alpha k/2}\le \frac{2k\gamma }{\alpha k/2}=\frac{4n}{{\alpha }^{2}k}.$ This immediately gives ${\alpha }^2\beta \le 4n/k$. Thus the exact tradeoff in Theorem 12 is achieved, and this finishes the proof of Claim 1. $\mathrm{⊲}$

The randomized algorithm is very simple: it selects a set of $\alpha k$ vantage points uniformly at random (without repetition) from $S(\sqrt{n/k})$. The proof is similar to the deterministic case. Let $m$ be the number of edge capacities revealed in $OPT$. Let us consider the expected number of edges covered by the $\alpha k$ vantage points. Note that $S(\sqrt{n/k})$ has $\sqrt{nk}$ vertices; if all selected as vantage points, would reveal at least $m-k\sqrt{n/k}=m-\sqrt{nk}$ many edges revealed by OPT. By linearity of expectation the expected number of edges that are revealed by a random choice of $\alpha k$ vantage points from $S(\sqrt{n/k})$ is at least $\frac{\alpha k}{\sqrt{nk}}(m-\sqrt{nk}).$ Again we consider two cases. If $m\ge 2\sqrt{nk}$, $m-\sqrt{nk}\ge m/2$. Thus $\beta \le 2\sqrt{nk}/(\alpha k)$, or, equivalently, $\alpha \beta \le 2\sqrt{n/k}$. If $m\le 2\sqrt{nk}$, our algorithm reveals at least $\alpha k/2$ edges since we select $\alpha k$ vantage points. Thus $\beta \le 2m/(\alpha k)\le 4\sqrt{(n/k)}/\alpha$. Or, $\alpha \beta \le 4\sqrt{(n/k)}$. This finishes the proof. $\mathrm{⊲}$ $◀$

We remark that all algorithms are non-adaptive with polynomial run time. This is slightly surprising, since the lower bounds were on algorithms not limited by computation. We conjecture that while for trees such non-adaptive algorithms suffice, adaptivity may be needed to achieve the tradeoffs (if it is possible at all) for general graphs.

We observed in the beginning of this section that for general graphs, the trivial algorithm achieves $\alpha \beta =O(n)$, and if this is tight, a matching lower bound would involve instances with cycles. However, we show next that such an instance cannot be planar. We leave as an interesting open question whether one can design a deterministic algorithm for general graph with $\alpha \beta =o(n)$.