Hardness of approximation

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This article accompanies the talk given by the author at the International Congress of Mathematicians, 2014. The article sketches some connections between approximability of NP-complete problems, analysis and geometry, and the role played by the Unique Games Conjecture in facilitating these connections. For a more extensive introduction to the topic, the reader is referred to survey articles [39, 40, 64].

Original languageEnglish (US)
Title of host publicationPlenary Lectures and Ceremonies
EditorsSun Young Jang, Young Rock Kim, Dae-Woong Lee, Ikkwon Yie
PublisherKYUNG MOON SA Co. Ltd.
Pages711-728
Number of pages18
ISBN (Electronic)9788961058049
StatePublished - 2014
Event2014 International Congress of Mathematicans, ICM 2014 - Seoul, Korea, Republic of
Duration: Aug 13 2014Aug 21 2014

Publication series

NameProceeding of the International Congress of Mathematicans, ICM 2014
Volume1

Conference

Conference2014 International Congress of Mathematicans, ICM 2014
CountryKorea, Republic of
CitySeoul
Period8/13/148/21/14

Keywords

  • Approximation algorithms
  • Discrete Fourier analysis
  • Inapproximability
  • NP-completeness
  • Probabilistically Checkable Proofs

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Hardness of approximation'. Together they form a unique fingerprint.

Cite this