论文标题
在线$ k $ -taxi通过双重覆盖范围和时间倒流原始偶尔
Online $k$-Taxi via Double Coverage and Time-Reverse Primal-Dual
论文作者
论文摘要
我们考虑在线$ k $ -taxi问题，这是$ k $ - 服务器问题的概括，其中$ k $服务器位于公制空间中。一系列请求逐一揭示，其中每个请求是两点，代表乘客的旅行请求的开始和目的地。目的是满足所有要求，同时最大程度地减少距离旅行的距离而无需携带乘客。 我们表明，经典的双重覆盖算法的竞争比率为$ 2^k-1 $在HSTS上，与最近的下界相匹配确定性算法。对于有界深度的HST，竞争比率要好得多，我们获得了紧密的界限。当深度为$ d \ ll k $时，这些界限约为$ k^d/d！$。根据标准嵌入结果，我们获得了具有（多项式）竞争比$ o（k^cδ^{1/c} \log_Δn）$的随机算法，其中$Δ$是倍数，$ c \ ge 1 $是任意的正透明常数。先前唯一已知的界限是$ O（2^k \ log n）$。对于一般（加权）树指标，我们证明，对于任何固定深度$ d $，双重覆盖率的竞争比为$θ（k^d）$，但与HSTS不同，它不受$ 2^k-1 $的限制。 我们通过双重拟合分析获得结果，其中双重解决方案是及时逐步向后构造的。与在线原始二元分析的典型远期时间方法不同，这使我们可以在分配双重变量时结合过去和将来的信息。我们认为，此方法对于其他问题也很有用。使用此技术，我们还提供了双重证明，证明了$ k $ cottivilities the Trees上的$ K $ - 服务器问题的双重覆盖范围。
We consider the online $k$-taxi problem, a generalization of the $k$-server problem, in which $k$ servers are located in a metric space. A sequence of requests is revealed one by one, where each request is a pair of two points, representing the start and destination of a travel request by a passenger. The goal is to serve all requests while minimizing the distance traveled without carrying a passenger. We show that the classic Double Coverage algorithm has competitive ratio $2^k-1$ on HSTs, matching a recent lower bound for deterministic algorithms. For bounded depth HSTs, the competitive ratio turns out to be much better and we obtain tight bounds. When the depth is $d\ll k$, these bounds are approximately $k^d/d!$. By standard embedding results, we obtain a randomized algorithm for arbitrary $n$-point metrics with (polynomial) competitive ratio $O(k^cΔ^{1/c}\log_Δ n)$, where $Δ$ is the aspect ratio and $c\ge 1$ is an arbitrary positive integer constant. The only previous known bound was $O(2^k\log n)$. For general (weighted) tree metrics, we prove the competitive ratio of Double Coverage to be $Θ(k^d)$ for any fixed depth $d$, but unlike on HSTs it is not bounded by $2^k-1$. We obtain our results by a dual fitting analysis where the dual solution is constructed step-by-step backwards in time. Unlike the forward-time approach typical of online primal-dual analyses, this allows us to combine information from the past and the future when assigning dual variables. We believe this method can be useful also for other problems. Using this technique, we also provide a dual fitting proof of the $k$-competitiveness of Double Coverage for the $k$-server problem on trees.
