Direction preserving zero point computing and applications

Xiaotie Deng; Qi Qi; Jie Zhang

doi:10.1007/978-3-642-10841-9_37

Direction preserving zero point computing and applications

Xiaotie Deng, Qi Qi, Jie Zhang

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

1 Citation (SciVal)

Abstract

We study the connection between the direction preserving zero point and the discrete Brouwer fixed point in terms of their computational complexity. As a result, we derive a PPAD-completeness proof for finding a direction preserving zero point, and a matching oracle complexity bound for computing a discrete Brouwer's fixed point. Building upon the connection between the two types of combinatorial structures for Brouwer's continuous fixed point theorem, we derive an immediate proof that TUCKER is PPAD-complete for all constant dimensions, extending the results of Pálvölgyi for 2D case [20] and Papadimitriou for 3D case [21]. In addition, we obtain a matching algorithmic bound for TUCKER in the oracle model.

Original language	English
Title of host publication	Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings
Editors	S. Leonardi
Place of Publication	Berlin, Germany
Publisher	Springer Berlin
Pages	410-421
Number of pages	12
ISBN (Electronic)	9783642108419
ISBN (Print)	9783642108402
DOIs	https://doi.org/10.1007/978-3-642-10841-9_37
Publication status	Published - 31 Dec 2009
Event	5th International Workshop on Internet and Network Economics, WINE 2009 - Rome, Italy Duration: 14 Dec 2009 → 18 Dec 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5929 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th International Workshop on Internet and Network Economics, WINE 2009
Country/Territory	Italy
City	Rome
Period	14/12/09 → 18/12/09

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-10841-9_37

Cite this

Deng, X., Qi, Q., & Zhang, J. (2009). Direction preserving zero point computing and applications. In S. Leonardi (Ed.), Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings (pp. 410-421). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5929 LNCS). Springer Berlin. https://doi.org/10.1007/978-3-642-10841-9_37

Direction preserving zero point computing and applications. / Deng, Xiaotie; Qi, Qi; Zhang, Jie.
Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings. ed. / S. Leonardi. Berlin, Germany: Springer Berlin, 2009. p. 410-421 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5929 LNCS).

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

Deng, X, Qi, Q & Zhang, J 2009, Direction preserving zero point computing and applications. in S Leonardi (ed.), Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5929 LNCS, Springer Berlin, Berlin, Germany, pp. 410-421, 5th International Workshop on Internet and Network Economics, WINE 2009, Rome, Italy, 14/12/09. https://doi.org/10.1007/978-3-642-10841-9_37

Deng X, Qi Q, Zhang J. Direction preserving zero point computing and applications. In Leonardi S, editor, Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings. Berlin, Germany: Springer Berlin. 2009. p. 410-421. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-10841-9_37

Deng, Xiaotie ; Qi, Qi ; Zhang, Jie. / Direction preserving zero point computing and applications. Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings. editor / S. Leonardi. Berlin, Germany : Springer Berlin, 2009. pp. 410-421 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3906f56ca2a940e69946390cc769b65c,

title = "Direction preserving zero point computing and applications",

abstract = "We study the connection between the direction preserving zero point and the discrete Brouwer fixed point in terms of their computational complexity. As a result, we derive a PPAD-completeness proof for finding a direction preserving zero point, and a matching oracle complexity bound for computing a discrete Brouwer's fixed point. Building upon the connection between the two types of combinatorial structures for Brouwer's continuous fixed point theorem, we derive an immediate proof that TUCKER is PPAD-complete for all constant dimensions, extending the results of P{\'a}lv{\"o}lgyi for 2D case [20] and Papadimitriou for 3D case [21]. In addition, we obtain a matching algorithmic bound for TUCKER in the oracle model.",

author = "Xiaotie Deng and Qi Qi and Jie Zhang",

year = "2009",

month = dec,

day = "31",

doi = "10.1007/978-3-642-10841-9_37",

language = "English",

isbn = "9783642108402",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Berlin",

pages = "410--421",

editor = "S. Leonardi",

booktitle = "Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings",

address = "Germany",

note = "5th International Workshop on Internet and Network Economics, WINE 2009 ; Conference date: 14-12-2009 Through 18-12-2009",

}

TY - GEN

T1 - Direction preserving zero point computing and applications

AU - Deng, Xiaotie

AU - Qi, Qi

AU - Zhang, Jie

PY - 2009/12/31

Y1 - 2009/12/31

N2 - We study the connection between the direction preserving zero point and the discrete Brouwer fixed point in terms of their computational complexity. As a result, we derive a PPAD-completeness proof for finding a direction preserving zero point, and a matching oracle complexity bound for computing a discrete Brouwer's fixed point. Building upon the connection between the two types of combinatorial structures for Brouwer's continuous fixed point theorem, we derive an immediate proof that TUCKER is PPAD-complete for all constant dimensions, extending the results of Pálvölgyi for 2D case [20] and Papadimitriou for 3D case [21]. In addition, we obtain a matching algorithmic bound for TUCKER in the oracle model.

AB - We study the connection between the direction preserving zero point and the discrete Brouwer fixed point in terms of their computational complexity. As a result, we derive a PPAD-completeness proof for finding a direction preserving zero point, and a matching oracle complexity bound for computing a discrete Brouwer's fixed point. Building upon the connection between the two types of combinatorial structures for Brouwer's continuous fixed point theorem, we derive an immediate proof that TUCKER is PPAD-complete for all constant dimensions, extending the results of Pálvölgyi for 2D case [20] and Papadimitriou for 3D case [21]. In addition, we obtain a matching algorithmic bound for TUCKER in the oracle model.

UR - http://www.scopus.com/inward/record.url?scp=76749088091&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-10841-9_37

DO - 10.1007/978-3-642-10841-9_37

M3 - Chapter in a published conference proceeding

AN - SCOPUS:76749088091

SN - 9783642108402

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 410

EP - 421

BT - Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings

A2 - Leonardi, S.

PB - Springer Berlin

CY - Berlin, Germany

T2 - 5th International Workshop on Internet and Network Economics, WINE 2009

Y2 - 14 December 2009 through 18 December 2009

ER -

Direction preserving zero point computing and applications

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this