Computational complexity of some maximum average weight problems with precedence constraints

Ulrich Faigle, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)
49 Downloads (Pure)

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 languageEnglish
Pages (from-to)688-693
Number of pages6
JournalOperations research
Volume42
Issue number4
DOIs
Publication statusPublished - 1994

Fingerprint Dive into the research topics of 'Computational complexity of some maximum average weight problems with precedence constraints'. Together they form a unique fingerprint.

  • Cite this