Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints

DOI10.1287/opre.42.4.688zbMath0815.90130OpenAlexW2033245488MaRDI QIDQ4319758

Ulrich Faigle, Walter Kern

Publication date: 12 January 1995

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/computational-complexity-of-some-maximum-average-weight-problems-with-precedence-constraints(fcb5a027-eca4-46df-9ece-52f60505272b).html

zbMATH Keywords

learningNP-completemaximum average weighttree-structured attributes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

Optimization problems with color-induced budget constraints, Optimizing mining complexes with multiple processing and transportation alternatives: an uncertainty-based approach, Output-polynomial enumeration of all fixed-cardinality ideals of a poset, respectively all fixed-cardinality subtrees of a tree., On a class of branching problems in broadcasting and distribution, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Locating tree-shaped facilities using the ordered median objective, Minimizing the number of tardy jobs with precedence constraints and agreeable due dates, Local search algorithms for the \(k\)-cardinality tree problem., Optimization Problems with Color-Induced Budget Constraints, An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs