Computational complexity of some maximum average weight problems with precedence constraints

Computational complexity of some maximum average weight problems with precedence constraints

0.00 Avg rating0 Votes
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: ,
Keywords: networks, programming: integer, programming: dynamic
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.

Reviews

Required fields are marked *. Your email address will not be published.