On convex body chasing
On convex body chasing
复制标题
凸身追击上
DOI：
10.1007/bf02189324
复制
发表时间：
1993
影响因子：
0.8
通讯作者：
N. Linial
中科院分区：
文献类型：
--
作者：
J. Friedman;N. Linial
在飞机上移动的播放器是以下类型的一系列指令：在Stepi中，指定了平面凸setfi，并且播放器必须移动到一个Infi。对于竞争性的玩家，即，对于任何序列，播放器的成本都在“离线”成本的恒定（乘法）因子之内（即，当我们提前知道Allfi时可能的成本最低）在任何欧几里得空间，甚至在所有度量空间中，都可以为此游戏制定类似的策略。作为thek-server问题，我们提醒了这些更普遍的问题。
A player moving in the plane is given a sequence of instructions of the following type: at stepi a planar convex setFi is specified, and the player has to move to a point inFi. The player is charged for the distance traveled. We provide a strategy for the player which is competitive, i.e., for any sequenceFi the cost to the player is within a constant (multiplicative) factor of the “off-line” cost (i.e., the least possible cost when allFi are known in advance). We conjecture that similar strategies can be developed for this game in any Euclidean space and perhaps even in all metric spaces. The analogous statement where convex sets are replaced by more general families of sets in a metric space includes many on-line/off-line problems such as thek-server problem; we make some remarks on these more general problems.