Journal article icon

Journal article

Discrete fixed points: models, complexities, and applications

Abstract:

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 computational complexity unification of the above problems gives us more choices in the study of different applications. As an example, by a reduction from DPZP, we derive asymptotically equal lower and upper bound for TUCKER in the oracle model. The s...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1287/moor.1110.0511

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Publisher:
INFORMS Publisher's website
Journal:
Mathematics of Operations Research Journal website
Volume:
36
Issue:
4
Pages:
636-652
Publication date:
2011-11-05
DOI:
EISSN:
1526-5471
ISSN:
0364-765X
URN:
uuid:f147538c-ca80-41e8-9677-53c24e1f70f4
Source identifiers:
573560
Local pid:
pubs:573560

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP