TY - GEN
T1 - On unique games with negative weights
AU - Cui, Peng
AU - Liu, Tian
AU - Xu, Ke
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/80051954606
U2 - 10.1007/978-3-642-22616-8_37
DO - 10.1007/978-3-642-22616-8_37
M3 - 会议稿件
AN - SCOPUS:80051954606
SN - 9783642226151
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 480
EP - 490
BT - Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings
T2 - 5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011
Y2 - 4 August 2011 through 6 August 2011
ER -