Access Restriction

Author Chen, Xi ♦ Deng, Xiaotie
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Approximate fixed point ♦ Lipschitz function ♦ Sperner's lemma ♦ Fixed point theorem
Abstract We prove a new discrete fixed point theorem for direction-preserving functions defined on integer points, based on a novel characterization of boundary conditions for the existence of fixed points. The theorem allows us to derive an improved algorithm for finding such a fixed point. We also develop a new lower bound proof technique. Together, they allow us to derive an asymptotic matching bound for the problem of finding a fixed point in a hypercube of any constantly bounded finite dimension. Exploring a linkage with the approximation version of the continuous fixed point problem, we obtain asymptotic matching bounds for the complexity of the approximate Brouwer fixed point problem in the continuous case for Lipschitz functions. It settles a fifteen-years-old open problem of Hirsch, Papadimitriou, and Vavasis by improving both the upper and lower bounds. Our characterization for the existence of a fixed point is also applicable to functions defined on nonconvex domains, which makes it a potentially useful tool for the design and analysis of algorithms for fixed points in general domains.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-08-06
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 55
Issue Number 3
Page Count 26
Starting Page 1
Ending Page 26

Open content in new tab

   Open content in new tab
Source: ACM Digital Library