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.
展开▼
