论文标题
共识划分以任意比率
Consensus Division in an Arbitrary Ratio
论文作者
论文摘要
我们考虑将线段段分隔为两个子集的问题，因此$ n $有限的度量均具有相同的子集值比率。让$α\在[0,1] $中表示所需的比率，这将概括为PPA结合共识问题，其中$α= \ frac {1} {2} $。 Stromquist和Woodall表明，对于任何$α$，都有使用$ 2N $的细分市场的解决方案。他们还表明，如果$α$是非理性的，那么上限几乎是最佳的。在这项工作中，我们详细阐述了理性值$α$的界限。对于$α= \ frac {\ ell} {k} $，我们显示了$ \ frac {k -1} {k -1} {k} {k} \ cdot 2n -o（1）$ cuts;我们还为大量有理$α$的子集获得了几乎匹配的上限。在计算方面，我们探索了其对可用剪辑数量的依赖性。更具体地说， 1。当需要每个实例的剪切数量最少时，对于任何$α$来说，问题都是NP-HARD； 2。对于有理$α= \ frac {\ ell} {k} $的大量子集，当$ \ frac {k-1} {k-1} {k} {k} \ cdot 2n $ cuts可用时，问题出在图灵减少下的ppa- $ k $中； 3。当允许$ 2N $削减时，该问题属于任何$α$的PPA；通常，如果$ 2（p-1）\ cdot \ frac {\ lceil p/2 \ rceil} {\ lfloor p/2 \ rfloor} \ cdot n $ cuts可用。
We consider the problem of partitioning a line segment into two subsets, so that $n$ finite measures all have the same ratio of values for the subsets. Letting $α\in[0,1]$ denote the desired ratio, this generalises the PPA-complete consensus-halving problem, in which $α=\frac{1}{2}$. Stromquist and Woodall showed that for any $α$, there exists a solution using $2n$ cuts of the segment. They also showed that if $α$ is irrational, that upper bound is almost optimal. In this work, we elaborate the bounds for rational values $α$. For $α= \frac{\ell}{k}$, we show a lower bound of $\frac{k-1}{k} \cdot 2n - O(1)$ cuts; we also obtain almost matching upper bounds for a large subset of rational $α$. On the computational side, we explore its dependence on the number of cuts available. More specifically, 1. when using the minimal number of cuts for each instance is required, the problem is NP-hard for any $α$; 2. for a large subset of rational $α= \frac{\ell}{k}$, when $\frac{k-1}{k} \cdot 2n$ cuts are available, the problem is in PPA-$k$ under Turing reduction; 3. when $2n$ cuts are allowed, the problem belongs to PPA for any $α$; more generally, the problem belong to PPA-$p$ for any prime $p$ if $2(p-1)\cdot \frac{\lceil p/2 \rceil}{\lfloor p/2 \rfloor} \cdot n$ cuts are available.
