Competitive Analysis of Online Path Selection: Impacts of Path Length, Topology, and System-Level Costs

For line networks, partition the line network $\mathcal{N}$ into $J=\lfloor\frac{N}{M}\rfloor$ disjoint lines $\mathcal{N}=\cup_{j}\mathcal{N}_{j}$, each containing $M$ consecutive edges and $M+1$ nodes. Requests can travel through at most two $M$-long lines. Those starting from $\mathcal{N}_{j}$ and ending in $\mathcal{N}_{j+1}$ are grouped in $I_{j}^{1}$, and those starting from $\mathcal{N}_{j}$ and ending in $\mathcal{N}_{j-1}$ are grouped in $I_{j}^{2}$. Let $I^{1}=\cup_{j}I_{j}^{1}$, $I^{2}=\cup_{j}I_{j}^{2}$ and $I=I^{1}\cup I^{2}$. Because the data transmission is usually unidirectional, requests in $I^{1}$ do not affect those in $I^{2}$. Built on this decoupling, we have

where $\textsf{OPT}(I)$ and $\textsf{ALG}(I)$ denotes the optimal revenue and the revenue of the online algorithm given the instance $I$. To simplify the notation, we drop the superscripts $1$ and $2$ from now on and focus on requests in one direction, e.g., $I_{j}$ is the set of requests that start from line network $\mathcal{N}_{j}$.

Let $\tilde{I}_{j}=I_{j-1}\cup I_{j},j\geq 2$. All requests in $\tilde{I}_{j}$ affect edges in $\mathcal{N}_{j}$. In the sequel, we focus on the upper bound for the ratio $\frac{\textsf{OPT}(I_{j})}{\textsf{ALG}(\tilde{I}_{j})}$ over instances in any $M$-long line network $\mathcal{N}_{j}$ because the competitive ratio is upper-bounded as:

Let $\tilde{\mathcal{N}}_{j}=\mathcal{N}_{j-1}\cup\mathcal{N}_{j}\cup\mathcal{N}_{j+1}$. Any edge in $\tilde{\mathcal{N}}_{j}$ can be possibly affected by requests in $\tilde{I}_{j}$. When there is no saturated edge in $\tilde{\mathcal{N}}_{j}$, i.e., no edge $e\in\tilde{\mathcal{N}}_{j}$ with $\omega_{e}^{(i)}>C_{e}-\epsilon$, after the $i$th request with $P_{i}\subset\tilde{\mathcal{N}}_{j}$ is routed, the value generated by the online algorithm increases by $\Delta\textsf{ALG}=v_{i}$. The increase to the optimal solution $\Delta\textsf{OPT}$ is upper-bounded by $\Delta C$ based on the weak duality, and we have

It follows that

because $r_{i}\sum_{e\in P_{i}}\lambda_{e}^{(i-1)}\leq v_{i}$, $\frac{v_{i}}{r_{i}d_{i}}\in[1,\bar{p}]$, and $x\left[\exp(\frac{\gamma}{x})-1\right]$ is decreasing in $[\gamma,\infty)$. When $r_{i}\leq\epsilon\leq\frac{C_{\min}}{\gamma}$, we have $\frac{\Delta C}{\Delta\textsf{ALG}}\leq 2\frac{C_{\min}}{r_{i}}\left(e^{\frac{r_{i}\gamma}{C_{\min}}}-1\right)+1\leq 2(e-1)\gamma+1$. Summing over $i$, we have $\textsf{OPT}(I_{j})\leq C(I_{j})$, and $\frac{\textsf{OPT}(I_{j})}{\textsf{ALG}(\tilde{I}_{j})}\leq\frac{C(I_{j})}{\textsf{ALG}(\tilde{I}_{j})}=2(e-1)\gamma+1$. Therefore, the competitive ratio for the case without edge saturation is $4(e-1)\gamma+2$.

When there exist almost-saturated edges (case with edge saturation), i.e., $\exists\tilde{e}\in\tilde{\mathcal{N}}_{j},w_{\tilde{e}}^{(i)}>C_{\tilde{e}}-\epsilon$, we need to show that the algorithm output is still lower-bounded by a portion of the optimal value, when requests are rejected due to the capacity limit instead of an insufficient value. Corollary 1 characterizes the largest possible lower bound by an optimization problem. Then we use Corollary 2 to bound the competitive ratio. Both corollaries are useful for the analysis of the tree network as well.

Assume that $M$ is a multiple of $m$. A commonly-employed lower bound of the algorithm output is the final total prices of all edges in the network as follows.

It then remains to bound the optimal revenue and final edge prices $\lambda_{e}^{(N)}$ for the case with edge saturation, which are dependent on the network topology and the edge capacities.

If $\forall e,C_{e}=C$, for a $3M$-long line network, the worst-case scenario is that each almost-saturated edge blocks an $M$-long request with the highest valuation. There are at most 3 such long and valuable requests blocked by three almost-saturated edges. Thus, the optimal revenue is upper-bounded by $3M\bar{p}C$, the online revenue is lower-bounded by

and the ratio $\frac{\textsf{OPT}(I_{j})}{\textsf{ALG}(\tilde{I}_{j})}$ is upper-bounded by $\frac{2(e-1)\gamma M\bar{p}}{\phi(C)+(2m-2)\phi(C/2)}$.

The overall competitive ratio is then upper-bounded by $\max\{4(e-1)\gamma+2,\frac{2(e-1)\gamma M\bar{p}}{\phi(C)+(2m-2)\phi(C/2)}\}=\max\{4(e-1)\gamma+2,\frac{2(e-1)\gamma M\bar{p}}{e^{\gamma}+(2m-2)e^{\gamma/2}+2m-1}\}=O(\ln\frac{M\bar{p}}{m})$ by choosing $\gamma=O(\ln\frac{M\bar{p}}{m})$.

For line networks with heterogeneous capacities, denote the minimum capacity in $\mathcal{N}_{j}$ as $\underline{C}_{j}$ and the edge as $\underline{e}_{j}$ and the maximum capacity of edges within $m$ reach of edge $\underline{e}_{j}$ in $\mathcal{N}_{j}$ as $\bar{C}_{j}$. The worst-case scenario happens when edge $\underline{e}_{j}$ is almost-saturated and blocks an $M$-long request. The optimal revenue is upper-bounded by $\sum_{k=j-1}^{j+1}M\bar{p}\underline{C}_{k}$, the online revenue is lower-bounded by

and the ratio $\frac{\textsf{OPT}(I_{j})}{\textsf{ALG}(\tilde{I}_{j})}$ is upper-bounded by $\frac{2(e-1)\gamma M\bar{p}}{e^{\gamma}-1+2(m-1)\beta(e^{\frac{\gamma}{2\beta}}-1)}$, where $\beta=\max_{j}\frac{\bar{C}_{j}}{\underline{C}_{j}}$. Thus, the overall competitive ratio is upper-bounded by $\max\{4(e-1)\gamma+2,\frac{2(e-1)\gamma M\bar{p}}{e^{\gamma}-1+2(m-1)\beta(e^{\frac{\gamma}{2\beta}}-1)}\}=O(\beta\ln(\frac{M\bar{p}}{2m\beta}+1))$ by choosing $\gamma=O(\beta\ln(\frac{M\bar{p}}{2m\beta}+1))$. When $\beta$ is large, $\frac{2(e-1)\gamma M\bar{p}}{e^{\gamma}-1+2(m-1)\beta(e^{\frac{\gamma}{2\beta}}-1)}$ is upper-bounded by $\frac{2(e-1)\gamma M\bar{p}}{e^{\gamma}-1}=O(\ln(M\bar{p}))$ by choosing $\gamma=O(\ln(M\bar{p}))$. Thus, the competitive ratio is upper-bounded by $\max\{O(\ln M\bar{p}),O(\beta\ln(\frac{M\bar{p}}{2m\beta}+1))\}$.

∎

We start with the case when all edges have the same capacity $C$. From Lemma 1, we have $\textsf{ALG}\geq\frac{\sum_{e}C\phi_{e}(\omega_{e}^{(N)})}{2(e-1)\gamma}$. The optimal revenue is upper-bounded by allocating the capacity of the top-level edge to the highest-valued requests: $\textsf{OPT}\leq M\bar{p}C$. If there is an edge that reaches the capacity, it will be the top-level edge, and there are at most $2^{k}$ edges at level $k$ among which the load is evenly distributed, then we have

The ratio for the case with edge saturation is then upper-bounded by $\frac{2(e-1)\gamma\bar{p}CM}{C\sum_{k=0}^{m-1}2^{k}(e^{\frac{\gamma}{2^{k}}}-1)}\leq\frac{2(e-1)\gamma\bar{p}M}{m2^{m-1}(e^{\frac{\gamma}{2^{m-1}}}-1)}$, and the competitive ratio is eventually bounded by $O(2^{m-1}\ln(\frac{M\bar{p}}{m\cdot 2^{m-1}}+1))$ by choosing $\gamma=O(2^{m-1}\ln(\frac{M\bar{p}}{m\cdot 2^{m-1}}+1))$.

We then consider the influence of heterogeneous capacities on the performance of our mechanism by studying the case where edges at the $i$th level are endowed with a capacity of $\frac{C}{2^{i}}$. In this case, edges of the first level may not be the first saturated. Let the first saturated edge be of the $l$th level ($l\leq m$) and $\phi_{k}(\omega)=e^{\frac{2^{k}\gamma\omega}{C}}-1$, the algorithmic output is lower-bounded in

The above inequalities hold for the following reasons. Saturating an edge of the $l$th level (with capacity $\frac{C}{2^{l}}$) leads to that each of the $l-1$ ancestor edges is consumed at least $\frac{C}{2^{l}}$, and edges of $m-l$ child levels are also saturated because each child edge only has one ancestor edge and the total capacities over an edge’s child edges are the same to its own capacity. The optimal value is upper-bounded as $\textsf{OPT}\leq\frac{M\bar{p}C}{2^{l}}$ because the bottleneck link is of capacity $\frac{C}{2^{l}}$.

The competitive ratio is then upper-bounded by $O(\max\{2^{l}\ln(\frac{M\bar{p}}{m2^{l}}+1),\ln(\frac{M\bar{p}}{m-l+1}+1)\})$. We thus complete the proof of Theorem 2. ∎

In a full binary tree, the source nodes of concern must be of depth $d\leq M-m$. For identical capacity case, the optimal value is upper-bounded by $M\bar{p}C$. Denote the saturated edge with the lowest level as $\underline{e}$ and the level of its parent node as $\underline{d}$. It is obvious that any ancestor edge of $\underline{e}$ is also saturated. The algorithm output ALG is lower-bounded by

The competitive ratio is upper-bounded by

by choosing $\gamma=O(2^{M-\underline{d}-1}\ln(\frac{M\bar{p}}{(M-\underline{d})2^{M-\underline{d}-1}}+1))$. Thus, the competitive ratio is upper-bounded by $O(\max_{x\in[m,M]}2^{x-1}\ln(\frac{M\bar{p}}{x2^{x-1}}+1))$.

For the case where the capacity of the $i$-th level edge is $\frac{C}{2^{i}}$, the optimal value is upper-bounded by $M\bar{p}\frac{C}{2^{\underline{d}}}$, where $\underline{d}$ is defined the same as above. The algorithmic output is lower-bounded in $2(e-1)\gamma\textsf{ALG}\geq\frac{C}{2^{\underline{d}}}\sum_{k=0}^{M-\underline{d}-1}\frac{C}{2^{k}}2^{k}(e^{\gamma}-1)$. The ratio for the saturated case is thus upper-bounded by $\frac{2(e-1)\gamma M\bar{p}\frac{C}{2^{\underline{d}}}}{\frac{C}{2^{\underline{d}}}\sum_{k=0}^{M-\underline{d}-1}\frac{C}{2^{k}}2^{k}(e^{\gamma}-1)}=\frac{2(e-1)\gamma M\bar{p}}{(M-\underline{d})(e^{\gamma}-1)}=O(\ln(1+\frac{M\bar{p}}{M-\underline{d}}))$ by choosing $\gamma=O(\ln(1+\frac{M\bar{p}}{M-\underline{d}}))$. Thus, the competitive ratio is upper-bounded by $O(\ln(1+\frac{M\bar{p}}{m}))$.

∎