论文标题
在Nisan-Ronen的猜想上
On the Nisan-Ronen conjecture
论文作者
论文摘要
Nisan-Ronen的猜想指出，将$ M $ M $任务分配给$ n $无关的机器时，没有实现MakePan最小化的真实机制，其近似值的近似值小于$ n $。自从其制定的二十年中，在解决它方面几乎没有取得进展，而最著名的下限仍然是一个小常数。这项工作通过显示$ 1+\ sqrt {n-1} $的下限来验证猜想。
The Nisan-Ronen conjecture states that no truthful mechanism for makespan-minimization when allocating $m$ tasks to $n$ unrelated machines can have approximation ratio less than $n$. Over more than two decades since its formulation, little progress has been made in resolving it and the best known lower bound is still a small constant. This work makes progress towards validating the conjecture by showing a lower bound of $1+\sqrt{n-1}$.
