Optimal bounds on finding fixed points of contraction mappings
Journal
Theoretical Computer Science
Journal Volume
411
Journal Issue
16-18
Pages
1742-1749
Date Issued
2010
Author(s)
Chang, C.-L.
Abstract
The Banach fixed-point theorem states that a contraction mapping on a complete metric space has a unique fixed point. Given an oracle access to a finite metric space (M, d) and a contraction mapping f : M → M on it, we show that the fixed point of f can be found with an expected O (sqrt(| M |)) oracle queries. We also show that every randomized algorithm for finding a fixed point must make an expected Ω (sqrt(| M |)) oracle queries to (M, d) and f for some finite metric space (M, d) and some contraction mapping f : M → M on it. As a generalization of the Banach fixed-point theorem, the Caristi-Kirk fixed-point theorem gives weaker conditions on (M, d) and f guaranteeing the existence of a fixed point of f. We show that every randomized algorithm that finds a fixed point must make the expected Ω (| M |) oracle queries to (M, d) and f for some finite metric space (M, d) and some function f : M → M satisfying the conditions of the Caristi-Kirk fixed-point theorem. © 2010 Elsevier B.V. All rights reserved.
The Banach fixed-point theorem states that a contraction mapping on a complete metric space has a unique fixed point. Given an oracle access to a finite metric space (M, d) and a contraction mapping f : M → M on it, we show that the fixed point of f can be found with an expected O (sqrt(| M |)) oracle queries. We also show that every randomized algorithm for finding a fixed point must make an expected Ω (sqrt(| M |)) oracle queries to (M, d) and f for some finite metric space (M, d) and some contraction mapping f : M → M on it. As a generalization of the Banach fixed-point theorem, the Caristi-Kirk fixed-point theorem gives weaker conditions on (M, d) and f guaranteeing the existence of a fixed point of f. We show that every randomized algorithm that finds a fixed point must make the expected Ω (| M |) oracle queries to (M, d) and f for some finite metric space (M, d) and some function f : M → M satisfying the conditions of the Caristi-Kirk fixed-point theorem. © 2010 Elsevier B.V. All rights reserved.
Type
journal article