The Knapsack Problem with Conflict Graphs.
Ulrich PferschyJoachim SchauerPublished in: J. Graph Algorithms Appl. (2009)
Keyphrases
- knapsack problem
- combinatorial optimization problems
- optimal solution
- test problems
- optimization problems
- dynamic programming
- exact algorithms
- greedy algorithm
- conflict resolution
- multidimensional knapsack problem
- np hard
- bicriteria
- heuristic solution
- linear programming relaxation
- continuous relaxation
- np hard problems
- greedy heuristic
- directed graph
- objective function
- decision variables
- search algorithm
- maximum profit