English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The problem of scheduling unrelated machines has been studied since theinception of algorithmic mechanism design \cite{NR99}. It is a resourceallocation problem that entails assigning $m$ tasks to $n$ machines forexecution. Machines are regarded as strategic agents who may lie about theirexecution costs so as to minimize their allocated workload. To address thesituation when monetary payment is not an option to compensate the machines'costs, \citeauthor{DBLP:journals/mst/Koutsoupias14} [2014] devised two\textit{truthful} mechanisms, K and P respectively, that achieve anapproximation ratio of $\frac{n+1}{2}$ and $n$, for social cost minimization.In addition, no truthful mechanism can achieve an approximation ratio betterthan $\frac{n+1}{2}$. Hence, mechanism K is optimal. While approximation ratioprovides a strong worst-case guarantee, it also limits us to a comprehensiveunderstanding of mechanism performance on various inputs. This paperinvestigates these two scheduling mechanisms beyond the worst case. We firstshow that mechanism K achieves a smaller social cost than mechanism P on everyinput. That is, mechanism K is pointwise better than mechanism P. Next, foreach task $j$, when machines' execution costs $t_i^j$ are independent andidentically drawn from a task-specific distribution $F^j(t)$, we show that theaverage-case approximation ratio of mechanism K converges to a constant. Thisbound is tight for mechanism K. For a better understanding of this distributiondependent constant, on the one hand, we estimate its value by plugging in a fewcommon distributions; on the other, we show that this converging bound improvesa known bound \cite{DBLP:conf/aaai/Zhang18} which only captures the single-tasksetting. Last, we find that the average-case approximation ratio of mechanism Pconverges to the same constant.

On Scheduling Mechanisms Beyond the Worst Case