论文标题
有效分裂措施和项链
Efficient Splitting of Measures and Necklaces
论文作者
论文摘要
我们为两个问题提供了近似算法，称为项链拆分和$ε$ - consensus分裂。在问题$ε$ -CONSENSUS分裂中，间隔$ [0，1] $和$ K $代理的$ N $非原子概率度量。目的是将间隔最多通过$ n（k-1）$切成碎片分成部分，并以大致公平的方式将其分配给$ k $ a的代理商，以便根据每种措施的任何两个代理商之间的差异，最多为$2ε/ k $。众所周知，即使对于$ε= 0 $也是可能的。项链拆分是$ε$ -CONSESUS拆分的离散版本。对于$ k = 2 $和一些绝对正常的$ε$，这两个问题都是ppad-hard。 我们考虑两种类型的近似值。第一个为每种类型的代理提供了对每种类型的阳性量度，最多最多$ n（k -1）$削减。第二个获得了大约公平的拆分，并尽可能少。除离线模型外，我们还考虑了在线模型，其中将间隔（或项链）作为流提供，并且必须当场进行切割和分发的决定。 对于第一种类型的近似值，我们描述了一种有效的算法，该算法至少为每个度量的每种量表至少$ \ frac {1} {nk} $，甚至在线工作。对于第二种类型的近似值，我们提供了一种有效的在线算法，该算法使$ \ text {poly}（n，k，ε）$ cuts和一个使$ o的离线算法（nk \ log \ frac {k} k}ε）$ cuts。我们还为在线模型中为$ k = 2 $代理而在线模型中所需的削减次数建立了较低界限，这表明我们在线算法中的削减次数是最佳的，可以达到对数因素。
We provide approximation algorithms for two problems, known as NECKLACE SPLITTING and $ε$-CONSENSUS SPLITTING. In the problem $ε$-CONSENSUS SPLITTING, there are $n$ non-atomic probability measures on the interval $[0, 1]$ and $k$ agents. The goal is to divide the interval, via at most $n (k-1)$ cuts, into pieces and distribute them to the $k$ agents in an approximately equitable way, so that the discrepancy between the shares of any two agents, according to each measure, is at most $2 ε/ k$. It is known that this is possible even for $ε= 0$. NECKLACE SPLITTING is a discrete version of $ε$-CONSENSUS SPLITTING. For $k = 2$ and some absolute positive constant $ε$, both of these problems are PPAD-hard. We consider two types of approximation. The first provides every agent a positive amount of measure of each type under the constraint of making at most $n (k - 1)$ cuts. The second obtains an approximately equitable split with as few cuts as possible. Apart from the offline model, we consider the online model as well, where the interval (or necklace) is presented as a stream, and decisions about cutting and distributing must be made on the spot. For the first type of approximation, we describe an efficient algorithm that gives every agent at least $\frac{1}{nk}$ of each measure and works even online. For the second type of approximation, we provide an efficient online algorithm that makes $\text{poly}(n, k, ε)$ cuts and an offline algorithm making $O(nk \log \frac{k}ε)$ cuts. We also establish lower bounds for the number of cuts required in the online model for both problems even for $k=2$ agents, showing that the number of cuts in our online algorithm is optimal up to a logarithmic factor.
