论文标题
具有转换的度量服务系统
Metrical Service Systems with Transformations
论文作者
论文摘要
我们考虑了基本的在线度量系统（MSS）问题的概括，其中可以在请求之间转换可行区域。在我们称之为T-MSS的问题中，算法在度量空间中保持了一个点，必须提供一系列请求。每个请求都是地图（转换）$ f_t \ colon a_t \ to to b_t $ to subsets $ a_t $和$ b_t $的公制空间。为了使用它，算法必须转到A_T $中的点$ a_t \，从而距离先前位置的距离。然后，应用转换，将算法的状态修改为$ f_t（a_t）$。这种转换可以建模，例如，对算法控制之外的环境的变化，因此，当应用转换时，我们不会向算法收取任何额外的成本。转换还允许建模在$ k $ -taxi问题中发生的请求。 我们表明，对于$α$ -lipschitz的转换，竞争比为$θ（α）^{n-2} $上的$ n $ - 点指标。在这里，上限是通过确定性算法来实现的，即使对于随机算法，下限也具有。对于$ k $ - taxi问题，我们证明了$ \ tilde o（（n \ log k）^2）$的竞争比率。对于追逐凸形的身体，我们表明，即使合同转换也没有竞争性算法。 问题T-MSS与以下深度数学问题有着惊人的联系：鉴于有限的度量空间$ m $，扩展$ \ hat m \ hat m \ supseteq m $所需的基数是什么，其中$ m $上的每个部分等轴测均扩展到自动形态？我们为特殊情况提供部分答案。
We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which we call T-MSS, an algorithm maintains a point in a metric space and has to serve a sequence of requests. Each request is a map (transformation) $f_t\colon A_t\to B_t$ between subsets $A_t$ and $B_t$ of the metric space. To serve it, the algorithm has to go to a point $a_t\in A_t$, paying the distance from its previous position. Then, the transformation is applied, modifying the algorithm's state to $f_t(a_t)$. Such transformations can model, e.g., changes to the environment that are outside of an algorithm's control, and we therefore do not charge any additional cost to the algorithm when the transformation is applied. The transformations also allow to model requests occurring in the $k$-taxi problem. We show that for $α$-Lipschitz transformations, the competitive ratio is $Θ(α)^{n-2}$ on $n$-point metrics. Here, the upper bound is achieved by a deterministic algorithm and the lower bound holds even for randomized algorithms. For the $k$-taxi problem, we prove a competitive ratio of $\tilde O((n\log k)^2)$. For chasing convex bodies, we show that even with contracting transformations no competitive algorithm exists. The problem T-MSS has a striking connection to the following deep mathematical question: Given a finite metric space $M$, what is the required cardinality of an extension $\hat M\supseteq M$ where each partial isometry on $M$ extends to an automorphism? We give partial answers for special cases.
