On unique games with negative weights

Peng Cui; Tian Liu; Ke Xu

doi:10.1007/978-3-642-22616-8_37

On unique games with negative weights

Peng Cui^*
, Tian Liu
, Ke Xu

^*Corresponding author for this work

School of Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings
Pages	480-490
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-22616-8_37
State	Published - 2011
Event	5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011 - Zhangjiajie, China Duration: 4 Aug 2011 → 6 Aug 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6831 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011
Country/Territory	China
City	Zhangjiajie
Period	4/08/11 → 6/08/11

Access to Document

10.1007/978-3-642-22616-8_37

Cite this

Cui, P., Liu, T., & Xu, K. (2011). On unique games with negative weights. In Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings (pp. 480-490). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6831 LNCS). https://doi.org/10.1007/978-3-642-22616-8_37

@inproceedings{741b5f467eb14434a0153c25bdeb407b,

title = "On unique games with negative weights",

abstract = "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.",

author = "Peng Cui and Tian Liu and Ke Xu",

year = "2011",

doi = "10.1007/978-3-642-22616-8\_37",

language = "英语",

isbn = "9783642226151",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "480--490",

booktitle = "Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings",

note = "5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011 ; Conference date: 04-08-2011 Through 06-08-2011",

}

Cui, P, Liu, T & Xu, K 2011, On unique games with negative weights. in Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6831 LNCS, pp. 480-490, 5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011, Zhangjiajie, China, 4/08/11. https://doi.org/10.1007/978-3-642-22616-8_37

On unique games with negative weights. / Cui, Peng; Liu, Tian; Xu, Ke.
Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings. 2011. p. 480-490 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6831 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

On unique games with negative weights

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this