论文标题
改进了以真实的安排的下限
Improved Lower Bounds for Truthful Scheduling
论文作者
论文摘要
Nisan and Ronen的开创性“算法机理设计”论文中引入了通过真实的机制来调度无关机器以最大程度地减少MakePan的问题。 Nisan和Ronen表明，有一种真实的机制提供$ \ min（m，n）$的近似值，其中$ n $是机器的数量，而$ m $是工作数。他们还证明，没有真实的机制可以提供大于$ 2 $的近似值。从那时起，Christodoulou，kotsoupias和vidali将下限提高到$ 1 +\ sqrt 2 \ 2.41 $，然后由Kotsoupias和Vidali $ 1 +ϕ \ $ 2.618 $。最近，Giannakopoulos，Hammerl和Pocas将下限提高到2.755美元。在本文中，对于每个常量的$δ> 0 $，我们进一步提高了$ 3-δ$。 请注意，即使机器和作业的数量很小，上限和下限之间的差距也存在。特别是，已知的$ 1+\ \ sqrt {2} $下限至少需要$ 3 $机器和5美元的作业。相比之下，我们显示的$ 2.2055 $的下限仅使用$ 3 $机器和$ 3 $的作业，以及仅使用$ 3 $机器和$ 4 $的$ 1+\ sqrt 2 $的下限。对于两台机器和两个作业的情况，我们显示了$ 2 $的下限。两台机器和两个作业的类似界限以前是知道的，但仅通过复杂的证据来表征所有真实的机制，这些机制在这种情况下提供了有限的近似值，而我们的新证明使用了简单而直接的方法。
The problem of scheduling unrelated machines by a truthful mechanism to minimize the makespan was introduced in the seminal "Algorithmic Mechanism Design" paper by Nisan and Ronen. Nisan and Ronen showed that there is a truthful mechanism that provides an approximation ratio of $\min(m,n)$, where $n$ is the number of machines and $m$ is the number of jobs. They also proved that no truthful mechanism can provide an approximation ratio better than $2$. Since then, the lower bound was improved to $1 +\sqrt 2 \approx 2.41$ by Christodoulou, Kotsoupias, and Vidali, and then to $1+ϕ\approx 2.618$ by Kotsoupias and Vidali. Very recently, the lower bound was improved to $2.755$ by Giannakopoulos, Hammerl, and Pocas. In this paper we further improve the bound to $3-δ$, for every constant $δ>0$. Note that a gap between the upper bound and the lower bounds exists even when the number of machines and jobs is very small. In particular, the known $1+\sqrt{2}$ lower bound requires at least $3$ machines and $5$ jobs. In contrast, we show a lower bound of $2.2055$ that uses only $3$ machines and $3$ jobs and a lower bound of $1+\sqrt 2$ that uses only $3$ machines and $4$ jobs. For the case of two machines and two jobs we show a lower bound of $2$. Similar bounds for two machines and two jobs were known before but only via complex proofs that characterized all truthful mechanisms that provide a finite approximation ratio in this setting, whereas our new proof uses a simple and direct approach.
