The complexity of algorithms computing game trees on random assignments

Chen Guang Liu; Kazuyuki Tanaka

doi:10.1007/978-3-540-72870-2_23

The complexity of algorithms computing game trees on random assignments

Chen Guang Liu, Kazuyuki Tanaka

SCI - Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

The complexity of algorithms for computing game trees on random assignments has been given substantial attention in the literature. In this line, we investigate the complexity of algorithms that compute a special class of game trees T₂^k from a new perspective -eigen-distribution. This particular distribution is defined as the worst distribution on assignments to variables of T₂^k regarding a best algorithm. In this paper, we show the eigen-distribution on assignments for T₂ ^k in two separate cases, where the assignments to leaves are independently distributed (ID) and correlated distributed(CD). Then we use eigen-distribution to derive the tight bound of the complexity of algorithms for T2*.

Original language	English
Title of host publication	Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings
Publisher	Springer Verlag
Pages	241-250
Number of pages	10
ISBN (Print)	9783540728689
DOIs	https://doi.org/10.1007/978-3-540-72870-2_23
Publication status	Published - 2007 Jan 1
Event	3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007 - Portland, OR, United States Duration: 2007 Jun 6 → 2007 Jun 8

Publication series

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

Other

Other	3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007
Country/Territory	United States
City	Portland, OR
Period	07/6/6 → 07/6/8

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-72870-2_23

Cite this

Liu, C. G., & Tanaka, K. (2007). The complexity of algorithms computing game trees on random assignments. In Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings (pp. 241-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4508 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-72870-2_23

The complexity of algorithms computing game trees on random assignments. / Liu, Chen Guang; Tanaka, Kazuyuki.
Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings. Springer Verlag, 2007. p. 241-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4508 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Liu, CG & Tanaka, K 2007, The complexity of algorithms computing game trees on random assignments. in Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4508 LNCS, Springer Verlag, pp. 241-250, 3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007, Portland, OR, United States, 07/6/6. https://doi.org/10.1007/978-3-540-72870-2_23

Liu CG, Tanaka K. The complexity of algorithms computing game trees on random assignments. In Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings. Springer Verlag. 2007. p. 241-250. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-72870-2_23

Liu, Chen Guang ; Tanaka, Kazuyuki. / The complexity of algorithms computing game trees on random assignments. Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings. Springer Verlag, 2007. pp. 241-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{84328a87af0245f582d1c09dda68a305,

title = "The complexity of algorithms computing game trees on random assignments",

abstract = "The complexity of algorithms for computing game trees on random assignments has been given substantial attention in the literature. In this line, we investigate the complexity of algorithms that compute a special class of game trees T2k from a new perspective -eigen-distribution. This particular distribution is defined as the worst distribution on assignments to variables of T2k regarding a best algorithm. In this paper, we show the eigen-distribution on assignments for T2 k in two separate cases, where the assignments to leaves are independently distributed (ID) and correlated distributed(CD). Then we use eigen-distribution to derive the tight bound of the complexity of algorithms for T2*.",

author = "Liu, {Chen Guang} and Kazuyuki Tanaka",

year = "2007",

month = jan,

day = "1",

doi = "10.1007/978-3-540-72870-2_23",

language = "English",

isbn = "9783540728689",

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

publisher = "Springer Verlag",

pages = "241--250",

booktitle = "Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings",

note = "3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007 ; Conference date: 06-06-2007 Through 08-06-2007",

}

TY - GEN

T1 - The complexity of algorithms computing game trees on random assignments

AU - Liu, Chen Guang

AU - Tanaka, Kazuyuki

PY - 2007/1/1

Y1 - 2007/1/1

N2 - The complexity of algorithms for computing game trees on random assignments has been given substantial attention in the literature. In this line, we investigate the complexity of algorithms that compute a special class of game trees T2k from a new perspective -eigen-distribution. This particular distribution is defined as the worst distribution on assignments to variables of T2k regarding a best algorithm. In this paper, we show the eigen-distribution on assignments for T2 k in two separate cases, where the assignments to leaves are independently distributed (ID) and correlated distributed(CD). Then we use eigen-distribution to derive the tight bound of the complexity of algorithms for T2*.

AB - The complexity of algorithms for computing game trees on random assignments has been given substantial attention in the literature. In this line, we investigate the complexity of algorithms that compute a special class of game trees T2k from a new perspective -eigen-distribution. This particular distribution is defined as the worst distribution on assignments to variables of T2k regarding a best algorithm. In this paper, we show the eigen-distribution on assignments for T2 k in two separate cases, where the assignments to leaves are independently distributed (ID) and correlated distributed(CD). Then we use eigen-distribution to derive the tight bound of the complexity of algorithms for T2*.

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

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

U2 - 10.1007/978-3-540-72870-2_23

DO - 10.1007/978-3-540-72870-2_23

M3 - Conference contribution

AN - SCOPUS:38149040105

SN - 9783540728689

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

SP - 241

EP - 250

BT - Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings

PB - Springer Verlag

T2 - 3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007

Y2 - 6 June 2007 through 8 June 2007

ER -

The complexity of algorithms computing game trees on random assignments

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this