Discrete fixed points : Models, complexities, and applications

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

6 Scopus Citations
View graph of relations

Author(s)

  • Xiaotie Deng
  • Qi Qi
  • Amin Saberi
  • Jie Zhang

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)636-652
Journal / PublicationMathematics of Operations Research
Volume36
Issue number4
Publication statusPublished - Nov 2011

Abstract

We study three discrete fixed point concept (SPERNER, DPZP, BROUWER) under two different models: the polynomial-time function model and the oracle function model. We fully characterize the computational complexities of these three problems. The computational complexity unification of the above problems gives us more choices in the study of different applications. As an example, by a reduction from DPZP, we derive asymptotically equal lower and upper bound for TUCKER in the oracle model. The same reduction also allows us to derive a single proof for the PPAD-completeness of TUCKER in any constant dimension, which is significantly simpler than the recent proofs. © 2011 INFORMS.

Research Area(s)

  • Algorithm, Fixed point, Sperner's lemma, Tucker's theorem

Citation Format(s)

Discrete fixed points : Models, complexities, and applications. / Deng, Xiaotie; Qi, Qi; Saberi, Amin; Zhang, Jie.

In: Mathematics of Operations Research, Vol. 36, No. 4, 11.2011, p. 636-652.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal