2021/10/22 by Antoine Méot, Méot, Antoine, Arnaud de Mesmay +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2110.11851
openalex publication_date 2021/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An approximation algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying a (1 - f(ε))-fraction of the constraints on any (1-ε)-satisfiable instance, where the loss function f is such that f(ε) → 0 as ε→ 0. Moreover, the runtime of a robust algorithm should not depend in any way on ε. In this paper, we present such an algorithm for Min-Unique-Games on complete graphs with q labels. Specifically, the loss function is f(ε) = (ε+ cε ε2), where cε is a constant depending on ε such that limε→ 0 cε = 16. The runtime of our algorithm is O(qn3) (with no dependence on ε) and can run in time O(qn2) using a randomized implementation with a slightly larger constant cε. Our algorithm is combinatorial and uses voting to find an assignment. It can furthermore be used to provide a PTAS for Min-Unique-Games on complete graphs, recovering a result of Karpinski and Schudy with a simpler algorithm and proof. We also prove NP-hardness for Min-Unique-Games on complete graphs and (using a randomized reduction) even in the case where the constraints form a cyclic permutation, which is also known as Min-Linear-Equations-mod-q on complete graphs.