The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions.
Abraham P. PunnenJasdeep DhahanPublished in: Algorithms (2024)
Keyphrases
- knapsack problem
- bipartite graph
- decision variables
- optimal solution
- combinatorial optimization problems
- optimization problems
- maximum matching
- exact algorithms
- dynamic programming
- greedy algorithm
- integer variables
- linear programming relaxation
- multidimensional knapsack problem
- bipartite graph matching
- greedy heuristic
- minimum weight
- continuous relaxation
- np hard
- maximum cardinality
- pairwise
- mutual reinforcement
- link prediction
- lp relaxation
- implicit enumeration
- constraint satisfaction
- maximum profit
- global constraints
- linear constraints
- neural network
- metaheuristic
- semi supervised
- evolutionary algorithm
- machine learning