A 2-to-1 game is a labeling optimization problem on a finite bipartite graph with left alphabet 
and right alphabet 
, for a positive
integer 
.
Each edge occurrence 
carries a function 
from the left alphabet
to the right alphabet, with exactly two elements in
every fiber. Parallel edge
occurrences may carry different functions. For example,
is allowed when 
. A labeling satisfies 
when 
.
The value is the maximum fraction of satisfied occurrences
in a nonempty list of constraints (Trevisan 2008).
2-to-1 Game
See also
NP-Hard Problem, Unique Game, Unique Games ConjectureExplore with Wolfram|Alpha
References
Trevisan, L. "Approximation Algorithms for Unique Games." Theory Comput. 4, 111-128, 2008. https://doi.org/10.4086/toc.2008.v004a005.Cite this as:
Weisstein, Eric W. "2-to-1 Game." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/2-to-1Game.html