On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering

DOI10.1016/j.tcs.2018.04.021zbMath1395.68147OpenAlexW2801809571MaRDI QIDQ1637226

Yinyu Ye, Chuangyin Dang

Publication date: 7 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.04.021

zbMATH Keywords

triangulationfixed pointinteger labelingincreasing mappingPPATarski's fixed-point theoremsimplicial methodcomponentwise orderinglattice of integer points

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Complete lattices, completions (06B23) Fixed points and coincidences in algebraic topology (55M20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of Tarski's fixed point theorem
• Finding all equilibria in games of strategic complements
• The computation of fixed points and applications
• On the complexity of the parity argument and other inefficient proofs of existence
• Triangulations and simplicial methods
• Piecewise linear methods for nonlinear equations and optimization
• Core many-to-one matchings by fixed-point methods
• Simplizialzerlegungen von beschränkter Flachheit
• A lattice-theoretical fixpoint theorem and its applications
• A Simplicial Approach to the Determination of an Integer Point of a Simplex
• Rationalizability, Learning, and Equilibrium in Games with Strategic Complementarities
• Settling the complexity of computing two-player Nash equilibria
• An Arbitrary Starting Homotopy-Like Simplicial Algorithm for Computing an Integer Point in a Class of Polytopes
• Polynomial-Time Aggregation of Integer Programming Problems
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• A restart algorithm for computing fixed points without an extra dimension
• Monotone Comparative Statics
• Homotopies for computation of fixed points
• The Approximation of Fixed Points of a Continuous Mapping
• SIMPLICIAL APPROXIMATION OF FIXED POINTS
• Homotopies for computation of fixed points on unbounded regions
• A Fixed-Point Approach to Stable Matchings and Some Applications