Negative Weights Make Unique Games Harder

Details Negative Weights Make Unique Games Harder Negative Weights Make Unique Games Harder

2012-04-10

arxiv.org/abs/1204.2026v1

Computer Science

Computational Complexity

6 pages, 1 figure

Scientific paper

In the second paper of this series, the author introduces GUGP($\rho$) model, which is a generalization of UGP where the weights of edges are allowed to be negative, and the magnitude of the total weight of all satisfied negative edges is no more than $\rho$ times the total weight of all positive edges. The author shows a gap amplification theorem on $(c,s)$-approximation NP-hardness of GUGP($\rho$). The theorem states that the $(c,s)$-approximation NP-hardness of UGP implies the $((\rho+1)c-\rho,(\rho+1)s-\rho)$-approximation NP-hardness of GUGP($\rho$) for any $\rho>0$, which confirms that the region of $(c,s)$-approximation NP-hardness of GUGP($\rho$) is significantly larger than the known region of $(c,s)$-approximation NP-hardness of UGP. In addition, the author presents another gap amplification theorem assuming a to-be-proven parallel repetition lemma, which claims harder approximation of GUGP($\rho$) than the first theorem from the $(c,s)$-approximation NP-hardness of UGP satisfying $1-c<\alpha(1-s)$, where $\alpha>0$ is a universal constant.

Affiliated with

Also associated with

No associations

Rating

Negative Weights Make Unique Games Harder 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 Negative Weights Make Unique Games Harder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Negative Weights Make Unique Games Harder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-643978