Local search efficiency limits for task assignment with server constraints

Exact Locality Gaps for Matchable Semi-Matchings

Data Structures and AlgorithmsDiscrete Mathematics

Summary

The paper studies how well tasks can be assigned to servers when you only improve the assignment by small changes at a time. It shows exactly how inefficient these locally optimized assignments can be compared to the best possible overall assignment. The authors provide formulas that describe the worst-case inefficiency depending on how many tasks you can reassign at once and various load limits on servers. Surprisingly, the worst cases happen even with very simple eligibility constraints where each task has only two possible servers. Their work gives precise guarantees about how good or bad locally optimal assignments can get in practical scheduling situations.

What this means in practice

  • For network schedulers: Design scheduling algorithms accounting for local search limits under simple task-to-server constraints.
  • For data center operators: Evaluate task reassignments’ impact on completion time to avoid inefficient local task placements.

A theory result. No direct application yet.

Authors

Marek Gałązka, Hanna Wdowicka

Abstract

An assignment of tasks to servers can resist every small improvement and still make tasks wait longer than necessary. We determine exactly how inefficient such an assignment can be when each task requires one unit of service and the eligibility constraints permit all tasks to use distinct servers. For every move size $r$ and maximum current server load $K$, we give a closed formula for the worst ratio between locally optimal and globally optimal total completion time. Local optimality here allows every feasible reassignment changing at most $r$ tasks. Every finite-cap bound is attained on a tree where each task has at most two eligible servers. Thus the worst behavior already occurs under simple eligibility constraints. At load cap two, the exact ratio is $1+1/(r+2)$, attained on a path with $r+2$ tasks. Without a load cap, the worst-case supremum is $3/2$ for single-task moves and approximately $1.294503159$ for two-task moves; its excess above one is $1/(r+2)+O(2^{-r}/r)$ as $r$ grows. The proof uses an explicit rational potential on a comparison graph and matching extremal constructions. These results give sharp guarantees for bounded-size local search on matchable semi-matchings, including exact guarantees under degree bounds.
View PDFOpen arXiv