Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 688-693 |
| Number of pages | 6 |
| Journal | Operations research |
| Volume | 42 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 1994 |