NDLI: Matching algorithmic bounds for finding a Brouwer fixed point

Content Provider	ACM Digital Library
Author	Chen, Xi Deng, Xiaotie
Copyright Year	2008
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.
Starting Page	1
Ending Page	26
Page Count	26
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/1379759.1379761
Journal	Journal of the ACM (JACM)
Volume Number	55
Issue Number	3
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-08-06
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximate fixed point Lipschitz function Sperner's lemma Fixed point theorem
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On algorithms for discrete and approximate brouwer fixed points

Sperner's Lemma, the Brouwer Fixed-Point Theorem, and Cohomology

Settling the complexity of computing two-player Nash equilibria

Sperner's Lemma, The Brouwer Fixed Point Theorem, the Kakutani Fixed Point Theorem, and Their Applications in Social Sciences

Lower Bounds for Distributed Maximum-Finding Algorithms

On Algorithms for Discrete and Approximate Brouwer Fixed Points (2005)

Improved Distributed Approximate Matching

Nonlinear pattern matching in trees

Polynomial Bounds for the Grid-Minor Theorem

Matching algorithmic bounds for finding a Brouwer fixed point

Similar Documents

On algorithms for discrete and approximate brouwer fixed points

Sperner's Lemma, the Brouwer Fixed-Point Theorem, and Cohomology

Settling the complexity of computing two-player Nash equilibria

Sperner's Lemma, The Brouwer Fixed Point Theorem, the Kakutani Fixed Point Theorem, and Their Applications in Social Sciences

Lower Bounds for Distributed Maximum-Finding Algorithms

On Algorithms for Discrete and Approximate Brouwer Fixed Points (2005)

Improved Distributed Approximate Matching

Nonlinear pattern matching in trees

Polynomial Bounds for the Grid-Minor Theorem

Matching algorithmic bounds for finding a Brouwer fixed point