Volume 8 - Issue 16
Generalized Unique Game Problem
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.
Paper Details
PaperID: 84866538023
Author's Name: Cui, P.
Volume: Volume 8
Issues: Issue 16
Keywords: Approximation algorithms, Computational complexity, Unique Game Conjecture
Year: 2012
Month: August
Pages: 6551 - 6557