COMPUTATIONAL-COMPLEXITY OF SOME MAXIMUM AVERAGE WEIGHT PROBLEMS WITH PRECEDENCE CONSTRAINTS
成果类型：
Article
署名作者：
FAIGLE, U; KERN, W
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.42.4.688
发表日期：
1994
页码：
688-693
关键词：
摘要：
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.