On unique games with negative weights. (English)
Wang, Weifan (ed.) et al., Combinatorial optimization and applications. 5th international conference, COCOA 2011, Zhangjiajie, China, August 4‒6, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22615-1/pbk). Lecture Notes in Computer Science 6831, 480-490 (2011).
Summary: In this paper, the authors define Generalized Unique Game Problem (GUGP), where weights of the edges are allowed to be negative. Focuses are made on two special types of GUGP, GUGP-NWA, where the weights of all edges are negative, and GUGP-PWT($ρ$), where the total weight of all edges are positive and the negative/positive ratio is at most $ρ$. The authors investigate the counterpart of the Unique Game Conjecture on GUGP-PWT($ρ$). The authors prove Unique Game Conjecture holds true on GUGP-PWT(1) by reducing the parallel repetition of Max 3-Cut Problem to GUGP-PWT(1), and Unique Game Conjecture holds true on GUGP-PWT(1/2) if the 2-to-1 Conjecture holds true. The authors pose an open problem whether Unique Game Conjecture holds true on GUGP-PWT($ρ$) with $0 < ρ< 1$.