TY - BOOK
T1 - Computational complexity of some maximum average weight problems with precedence constraints
AU - Faigle, Ulrich
AU - Kern, Walter
PY - 1991
Y1 - 1991
N2 - 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.
AB - 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.
M3 - Report
T3 - Memorandum
BT - Computational complexity of some maximum average weight problems with precedence constraints
PB - University of Twente
CY - Enschede
ER -