The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications

✍ Scribed by David Nehme; Yu Gang

• Book ID: 104294697
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 790 KB
• Volume: 74
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00015-7

✦ Synopsis

Given a hypergrdph with values on the hyperedges, the problem of finding a subhypergraph of maximum value subject to cardinality and precedence constraints on the nodes has applications ranging from partitioning fields in a database, to loading tools on a machine in a flexible manufacturing environment, to investment selection. For any instance of such a problem, consider the corresponding undirected graph G' = (V, E') with E' containing all pairs of nodes that either have a direct precedence relationship or are common to at least one hyperedge. Let n = 1 VI, and let s be the number of connected components of G'. We present an exact, 0(n2 logn) dynamic programming based algorithm for the case where G' is a forest (IE'l = n -s). By extending the result, we derive an exact, polynomial-time algorithm for cases where IL?'1 <n -s + c( logn, for any constant c(. These algorithms significantly improved the complexity and enlarged the application scope of the best existing algorithms. Finally, we show that the case where lE'l = O(n -s + d) is NP-hard, even when G' is connected and bipartite and the hyperedges all have unit value.