History


Please fill in your query. A complete syntax description you will find on the General Help page.
On unique games with negative weights. (English)
Wang, Weifan (ed.) et al., Combinatorial optimization and applications. 5th international conference, COCOA 2011, Zhangjiajie, China, August 4‒6, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22615-1/pbk). Lecture Notes in Computer Science 6831, 480-490 (2011).
Summary: 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$.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!