{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T10:44:09Z","timestamp":1771757049730,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["60553001"],"award-info":[{"award-number":["60553001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["CityU 112707"],"award-info":[{"award-number":["CityU 112707"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2003CB3178072004CB318108"],"award-info":[{"award-number":["2003CB3178072004CB318108"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2007CB8079002007CB807901"],"award-info":[{"award-number":["2007CB8079002007CB807901"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,7]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/1379759.1379761","type":"journal-article","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T13:35:10Z","timestamp":1217943310000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Matching algorithmic bounds for finding a Brouwer fixed point"],"prefix":"10.1145","volume":"55","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaotie","family":"Deng","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, Computer Society Press","author":"Altman E."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907353"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-3-1-133-181"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456931"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 12th Annual European Symposium on Algorithms. Springer-Verlag","author":"Chen N."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69733-6_18"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.53"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages and Programming. Springer-Verlag","author":"Codenotti B."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780618"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509920"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00011-4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007431"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE, Computer Society Press","author":"Devanur N."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584975"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1999.0504"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4068(03)00007-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmateco.2005.03.001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.6"},{"key":"e_1_2_1_20_1","unstructured":"Jain K. Mahdian M. and Saberi A. 2003. Approximating market equilibria. In Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 7th International Workshop on Randomization and Approximation Techniques in Computer Science. Springer-Verlag New York 861--869.  Jain K. Mahdian M. and Saberi A. 2003. Approximating market equilibria. In Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 7th International Workshop on Randomization and Approximation Techniques in Computer Science. Springer-Verlag New York 861--869."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM","author":"Jain K."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0713041"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1995.1011"},{"key":"e_1_2_1_24_1","unstructured":"Kronecker L. 1869. \u00dcber systeme von funktionen mehrerer variabeln. Monatsber. Berlin Akad. 159--193 and 688--698.  Kronecker L. 1869. \u00dcber systeme von funktionen mehrerer variabeln. Monatsber. Berlin Akad. 159--193 and 688--698."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.61.4.1238"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.815297"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779967"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00250708"},{"key":"e_1_2_1_29_1","unstructured":"Merrill O. 1972. Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-Continuous Point-to-Set Mappings. Ph.d. dissertation University of Michigan Ann Arbor MI.  Merrill O. 1972. Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-Continuous Point-to-Set Mappings. Ph.d. dissertation University of Michigan Ann Arbor MI."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"e_1_2_1_31_1","unstructured":"Ortega J. and Rheinbolt W. 1970. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press New York.   Ortega J. and Rheinbolt W. 1970. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press New York."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89602"},{"key":"e_1_2_1_33_1","unstructured":"Robinson C. 1999. Dynamical Systems Stability Symbolic Dynamics and Chaos. CRC Press.  Robinson C. 1999. Dynamical Systems Stability Symbolic Dynamics and Chaos. CRC Press."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0115116"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.2001.0606"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/838250.838255"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2003.06.001"},{"key":"e_1_2_1_38_1","volume-title":"Robustness in Identification and Control","author":"Sikorski K."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1993.1013"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(87)90008-2"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(76)90019-7"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Sperner E. 1928. Neuer beweis fur die invarianz der dimensionszahl und des gebietes. Abhandlungen aus dem Mathematischen Seminar Universitat Hamburg 6 265--272.  Sperner E. 1928. Neuer beweis fur die invarianz der dimensionszahl und des gebietes. Abhandlungen aus dem Mathematischen Seminar Universitat Hamburg 6 265--272.","DOI":"10.1007\/BF02940617"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. IEEE, Computer Society Press","author":"Spielman D."},{"key":"e_1_2_1_44_1","unstructured":"Yang Z. 1999. Computing equilibria and fixed points: The solution of nonlinear inequalities. Kluwer Academic Publishers Dordrecht.  Yang Z. 1999. Computing equilibria and fixed points: The solution of nonlinear inequalities. Kluwer Academic Publishers Dordrecht."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1379759.1379761","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1379759.1379761","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:45Z","timestamp":1750255065000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1379759.1379761"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["10.1145\/1379759.1379761"],"URL":"https:\/\/doi.org\/10.1145\/1379759.1379761","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7]]},"assertion":[{"value":"2005-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}