Xi Chen
ABSTRACT
We study the algorithmic complexity of the discrete fixed point problem and develop an asymptotic matching bound for a cube in any constantly bounded finite dimension. To obtain our upper bound, we derive a new fixed point theorem, based on a novel characterization of boundary conditions for the existence of fixed points.In addition, exploring a linkage with the approximation problem of the continuous fixed point problem, we obtain asymptotic matching bounds for complexity of the approximate Brouwer fixed point problem in the continuous case for Lipschitz functions that close a previous exponential gap. It settles a fifteen years old open problem of Hirsch, Papadimitriou and Vavasis by improving both the upper and lower bounds.Our new characterization for existence of a fixed point is also applicable to functions defined on non-convex domain and makes it a potentially useful tool for design and analysis of algorithms for fixed points in general domain.
- E. Altman, K. Avrachenkov, and C. Barakat. Tcp network calculus: The case of large delay-bandwidth product. In Proceedings of INFOCOM 2002.Google Scholar
Cross Ref
- K. Arrow and G. Debreu. Existence of an equilibrium for a competitive economy. Econometrica, 22:265--290, 1954.Google ScholarCross Ref
- S. Banach. Sur les opérations dans les ensembles abstraits et leur application aux Équations intégrales. Fundamenta Mathematicae, 3:133--181, 1922.Google ScholarCross Ref
- L. Brouwer. Über abbildung von mannigfaltigkeiten. Mathematische Annalen, 71:97--115, 1910.Google ScholarCross Ref
- N. Chen, X. Deng, X. Sun, and A. C.-C. Yao. Fisher equilibrium price with a class of concave utility functions. In ESA 2004, pages 169--179.Google ScholarCross Ref
- B. Codenotti and K. Varadarajan. Efficient computation of equilibrium prices for market with leontief utilities. In To appear in ICALP 2004.Google Scholar
- R. Cole, Y. Dodis, and T. Roughgarden. Pricing network edges for heterogeneous selfish users. In STOC 2003, pages 521--530. Google ScholarDigital Library
- X. Deng, C. Papadimitriou, and S. Safra. On the complexity of equilibria. In STOC 2002, pages 67--71. Google ScholarDigital Library
- X. Deng, C. Papadimitriou, and S. Safra. On the complexity of price equilibrium. Journal of Computer and System Sciences, 67(2):311--324, 2003. Google ScholarDigital Library
- N. Devanur. The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results. In STOC 2004, pages 519--528. Google ScholarDigital Library
- N. Devanur, C. Papadimitriou, A. Saberi, and V. Vazirani. Market equilibrium via a primal-dual-type algorithm. In FOCS 2002, pages 389--395. Google ScholarDigital Library
- B. Eaves. Homotopies for computation of fixed points. Mathematical Programming, 3:1--22, 1972.Google ScholarDigital Library
- M. Hirsch, C. Papadimitriou, and S. Vavasis. Exponential lower bounds for finding brouwer fixed points. J.Complexity, 5:379--416, 1989. Google ScholarDigital Library
- Z. Huang, L. Khachiyan, and K. Sikorski. Approximating fixed points of weakly contracting mappings. J.Complexity, 15:200--213, 1999. Google ScholarDigital Library
- T. Iimura. A discrete fixed point theorem and its applications. Journal of Mathematical Economics, 39:725--742, 2003.Google ScholarCross Ref
- T. Iimura, K. Murota, and A. Tamura. Discrete fixed point theorem reconsidered. METR, 9 2004.Google Scholar
- K. Jain. A polynomial time algorithm for computing the arrow-debreu market equilibrium for linear utilities. In FOCS 2004, pages 286--294. Google ScholarDigital Library
- K. Jain, M. Mahdian, and A. Saberi. Approximating market equilibria. In RANDOM-APPROX 2003, pages 98--108.Google ScholarCross Ref
- K. Jain, V. Vazirani, and Y. Ye. Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. In SODA 2005. Google ScholarDigital Library
- R. Kellogg, T. Li, and J. Yorke. Constructive proof of the brouwer fixed point theorem and computational results. SIAM J. Numer. Anal., 13:473--483, 1976.Google ScholarCross Ref
- K.-I. Ko. Computational complexity of fixed points and intersection points. J.Complexity, 11:265--292. Google ScholarDigital Library
- L. Kronecker. Über systeme von funktionen mehrerer variabeln. Montsh. Berl. Akad. Wiss., pages 159--163, 688--698, 1869.Google Scholar
- H. Kuhn. Simplicial approximation of fixed points. Proceedings of National Academy of Science, USA, 61:1238--1242, 1968.Google ScholarCross Ref
- S. Low. A duality model of tcp and queue management algorithms. IEEE/ACM Transactions on Networking, 11(4):525--536, 2003. Google ScholarDigital Library
- A. Mehta, S. Shenker, and V. Vazirani. Profit-maximizing multicast pricing by approximating fixed points. In ACM Conference on Electronic Commerce, pages 218--219, 2003. Google ScholarDigital Library
- G. Meinardus. Invarianz bei linearen approximationen. Arch. Rational. Mech. Anal., 14:301--303, 1963.Google ScholarCross Ref
- O. Merrill. Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-Continuous Point-to-Set Mappings. Phd thesis, University of Michigan, Annarbor, 1972.Google Scholar
- J. F. Nash. Equilibrium points in n-person games. In Proceedings of NAS, 1950.Google ScholarCross Ref
- C. Papadimitriou. On graph-theoretic lemmata and complexity classes. In STOC 1990, pages 794--801.Google ScholarDigital Library
- J. Ortega and W. Rheinbolt. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York, 1970. Google ScholarDigital Library
- C. Robinson. Dynamical Systems, Stability, Symbolic Dynamics, and Chaos. CRC Press, 1999.Google Scholar
- H. Scarf. The approximation of fixed points of a continuous mapping. SIAM Journal on Applied Mathematics, 15:997--1007, 1967.Google ScholarCross Ref
- S. Shellman and K. Sikorski. A two-dimensional bisection envelope algorithm for fixed points. J. Complexity, 18(2):641--659, 2002. Google ScholarDigital Library
- S. Shellman and K. Sikorski. Algorithm 825: A deep-cut bisection envelope algorithm for fixed points. ACM Trans. Math. Soft., 29(3):309--325, 2003. Google ScholarDigital Library
- S. Shellman and K. Sikorski. A recursive algorithm for the infinity-norm fixed point problem. J. Complexity, 19(6):799--834, 2003. Google ScholarDigital Library
- K. Sikorski. Fast algorithms for the computation of fixed points. In R. Milanese and A.Vicino, editors, In Robustness in Identification and Control, pages 49--59. Plenum Press, New York, 1989.Google ScholarCross Ref
- K. Sikorski, C. Tsay, and H. Wozniakowski. An ellipsoid algorithm for the computation of fixed points. J. Complexity, 9:181--200, 1993. Google ScholarDigital Library
- K. Sikorski and H. Wozniakowski. Complexity of fixed points, i. J. Complexity, 3(4):388--405, 1987. Google ScholarDigital Library
- S. Smale. A convergent process of price adjustment process and global newton methods. Journal on Mathematical Economics, 3:107--120, 1976.Google ScholarCross Ref
- E. Sperner. Neuer beweis fur die invarianz der dimensionszahl und des gebietes. Abhandlungen aus dem Mathematischen Seminar Universitat Hamburg, 6:265--272, 1928.Google Scholar
- D. Spielman and S.-H. Teng. Spectral partitioning works: Planar graphs and finite element meshes. In FOCS 1996, pages 96--105. Google ScholarDigital Library
- Z. Yang. Computing equilibria and fixed points: The solution of nonlinear inequalities. Kluwer Academic Publishers, Dordrecht, 1999.Google Scholar
Index Terms
- On algorithms for discrete and approximate brouwer fixed points
Recommendations
Matching algorithmic bounds for finding a Brouwer fixed point
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 ...
A Simplicial Approach for Discrete Fixed Point Theorems
We present a new discrete fixed point theorem based on a variation of the direction-preserving maps over simplicial structures. We show that the result is more general than the recent discrete fixed point theorem of Iimura et al. (J. Math. Econ. 41(8):...
Discrete Fixed Points: Models, Complexities, and Applications
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 ...
Comments