On Unique Games with Negative Weights

Abstract

In this paper, the author defines Generalized Unique Game Problem (GUGP), where weights of the edges are allowed to be negative. Two special types of GUGP are illuminated, 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 author investigates the counterpart of the Unique Game Conjecture on GUGP-PWT($ρ$). The author shows that Unique Game Conjecture on GUGP-PWT(1) holds true, and Unique Game Conjecture on GUGP-PWT(1/2) holds true, if the 2-to-1 Conjecture holds true. The author poses an open problem whether Unique Game Conjecture holds true on GUGP-PWT($ρ$) with $0<ρ<1$.

7 pages, accepted by COCOA 2011