The Complexity of Model Aggregation

Judy Goldsmith; Robert H. Sloan

The Complexity of Model Aggregation

Judy Goldsmith
, Robert H. Sloan

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

8 Scopus citations

Abstract

We show that the problem of transforming a structured Markov decision process (MDP) into a Bounded Inir.jval MDP is coNPp p-hard. ITI particular, the test for ε-homogencity. a necessary part of verifying any proposed partition, is coNP^pp-complete. This indicates that., without, further assumptions on the sorts of partitioning allowed or the structure of the original proportional MDP, this is not likely to be a practical approach. We also analyze the complexity of finding the minimal-size partition, and of the k-block partition existence problem. Finally, we show that the test for homogeneity of an exact partition is complete for coNP^pp which is the same class as coNP^pp. All of this analysis applies equally well to the process of partitioning the state space via Structured Value Iteration.

Original language	English
Title of host publication	Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000
Pages	122-129
Number of pages	8
ISBN (Electronic)	1577351118, 9781577351115
State	Published - 2000
Event	5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000 - Breckenridge, United States Duration: Apr 14 2000 → Apr 17 2000

Publication series

Name	Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000

Conference

Conference	5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000
Country/Territory	United States
City	Breckenridge
Period	4/14/00 → 4/17/00

Bibliographical note

Publisher Copyright:
Copyright © 2000, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.

Funding

This work partially supported by NSF grants CGR-9610348 and CCR-9800070. This work was done while the first, author was visiting TheU niversity of Ulinois at Chicago. The authors would like to thmlk Christopher This work partially supported by NSF grants CCR-9610348 and CCR-9800070. This work was done while the first, author was visiting The University of Illinois at Chicago. The authors would like to thank Christopher Lusena and Fred Green for useful conversations, Martin Mundhenk for first, observing that, the NP-hardness claim could be .strengthened, Jacobo Torán for making explicit a result implicit, in his dissertation and J A C M paper, and Hob Givan for writing up the \P-hardness proof and explaining (more than once!) what, they actually assumed in their implementations of the BMDP constructions.

Funders	Funder number
BMDP
NP-hardness
National Science Foundation (NSF)	CCR-9610348, CGR-9610348, CCR-9800070

ASJC Scopus subject areas

Artificial Intelligence

Cite this

@inproceedings{4e4d326b544f47db8c34f657438b0977,

title = "The Complexity of Model Aggregation",

abstract = "We show that the problem of transforming a structured Markov decision process (MDP) into a Bounded Inir.jval MDP is coNPp p-hard. ITI particular, the test for ε-homogencity. a necessary part of verifying any proposed partition, is coNPpp-complete. This indicates that., without, further assumptions on the sorts of partitioning allowed or the structure of the original proportional MDP, this is not likely to be a practical approach. We also analyze the complexity of finding the minimal-size partition, and of the k-block partition existence problem. Finally, we show that the test for homogeneity of an exact partition is complete for coNPpp which is the same class as coNPpp. All of this analysis applies equally well to the process of partitioning the state space via Structured Value Iteration.",

author = "Judy Goldsmith and Sloan, \{Robert H.\}",

note = "Publisher Copyright: Copyright {\textcopyright} 2000, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.; 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000 ; Conference date: 14-04-2000 Through 17-04-2000",

year = "2000",

language = "English",

series = "Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000",

pages = "122--129",

booktitle = "Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000",

}

Goldsmith, J & Sloan, RH 2000, The Complexity of Model Aggregation. in Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000. Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000, pp. 122-129, 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000, Breckenridge, United States, 4/14/00.

The Complexity of Model Aggregation. / Goldsmith, Judy; Sloan, Robert H.
Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000. 2000. p. 122-129 (Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000).

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

TY - GEN

T1 - The Complexity of Model Aggregation

AU - Goldsmith, Judy

AU - Sloan, Robert H.

PY - 2000

Y1 - 2000

N2 - We show that the problem of transforming a structured Markov decision process (MDP) into a Bounded Inir.jval MDP is coNPp p-hard. ITI particular, the test for ε-homogencity. a necessary part of verifying any proposed partition, is coNPpp-complete. This indicates that., without, further assumptions on the sorts of partitioning allowed or the structure of the original proportional MDP, this is not likely to be a practical approach. We also analyze the complexity of finding the minimal-size partition, and of the k-block partition existence problem. Finally, we show that the test for homogeneity of an exact partition is complete for coNPpp which is the same class as coNPpp. All of this analysis applies equally well to the process of partitioning the state space via Structured Value Iteration.

AB - We show that the problem of transforming a structured Markov decision process (MDP) into a Bounded Inir.jval MDP is coNPp p-hard. ITI particular, the test for ε-homogencity. a necessary part of verifying any proposed partition, is coNPpp-complete. This indicates that., without, further assumptions on the sorts of partitioning allowed or the structure of the original proportional MDP, this is not likely to be a practical approach. We also analyze the complexity of finding the minimal-size partition, and of the k-block partition existence problem. Finally, we show that the test for homogeneity of an exact partition is complete for coNPpp which is the same class as coNPpp. All of this analysis applies equally well to the process of partitioning the state space via Structured Value Iteration.

UR - https://www.scopus.com/pages/publications/0038256821

UR - https://www.scopus.com/pages/publications/0038256821#tab=citedBy

M3 - Conference contribution

AN - SCOPUS:0038256821

T3 - Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000

SP - 122

EP - 129

BT - Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000

T2 - 5th International Conference on Artificial Intelligence Planning Systems, AIPS 2000

Y2 - 14 April 2000 through 17 April 2000

ER -

The Complexity of Model Aggregation

Abstract

Publication series

Conference

Bibliographical note

Funding

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this