Article ID: | iaor199539 |
Country: | United States |
Volume: | 42 |
Issue: | 4 |
Start Page Number: | 688 |
End Page Number: | 693 |
Publication Date: | Jul 1994 |
Journal: | Operations Research |
Authors: | Kern Walter, Faigle Ulrich |
Keywords: | networks, programming: integer, programming: dynamic |
Maximum average weight ideal problems in ordered sets arise from modeling variants of the investment problem and, in particular, learning problems in the context of concepts with tree-structured attributes in artificial intelligence. Similarly, trying to construct tests with high reliability leads to a nontrivial maximum average weight ideal problem. This paper investigates the computational complexity and shows that the general problem is NP-complete. Important special cases (e.g., finding rooted subtrees of maximal average weight), however, can be handled with efficient algorithms.