How to Play Unique Games on Expanders

DOI10.1007/978-3-642-18318-8_17zbMath1314.68401arXiv0903.0367MaRDI QIDQ3075461

Yury Makarychev, Konstantin Makarychev

Publication date: 15 February 2011

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0903.0367

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

05C57: Games on graphs (graph-theoretic aspects)

Related Items

Tilings of rectangles with T-tetrominoes