Research output per year
Research output per year
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 |
|---|---|
| Place of Publication | Enschede |
| Publisher | University of Twente |
| Number of pages | 17 |
| Publication status | Published - 1991 |
Publication series
| Name | Memorandum |
|---|---|
| Publisher | University of Twente, Faculty of Applied Mathematics |
| No. | 899 |
| ISSN (Print) | 0921-1969 |
Fingerprint
Dive into the research topics of 'Computational complexity of some maximum average weight problems with precedence constraints'. Together they form a unique fingerprint.Research output
- 1 Article
-
Computational complexity of some maximum average weight problems with precedence constraints
Faigle, U. & Kern, W., 1994, In: Operations research. 42, 4, p. 688-693 6 p.Research output: Contribution to journal › Article › Academic › peer-review
Open AccessFile17 Citations (Scopus)161 Downloads (Pure)