On Unique Games with Negative Weights

Details On Unique Games with Negative Weights On Unique Games with Negative Weights

2011-02-28

arxiv.org/abs/1102.5605v3

Computer Science

Computational Complexity

11 pages, accepted by COCOA 2011

Scientific paper

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($\rho$), where the total weight of all edges are positive and the negative/positive ratio is at most $\rho$. The authors investigate the counterpart of the Unique Game Conjecture on GUGP-PWT($\rho$). 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($\rho$) with $0<\rho<1$.

Affiliated with

Also associated with

No associations

Rating

On Unique Games with Negative Weights does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Unique Games with Negative Weights, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Unique Games with Negative Weights will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-424802