The Knapsack Problem with Conflict Graphs
From MaRDI portal
Publication:3184613
DOI10.7155/jgaa.00186zbMath1194.68175OpenAlexW2140043891MaRDI QIDQ3184613
Ulrich Pferschy, Joachim Schauer
Publication date: 21 October 2009
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00186
Related Items
Quadratic bottleneck knapsack problems ⋮ Interdicting facilities in tree networks ⋮ Fair Packing of Independent Sets ⋮ Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach ⋮ A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs ⋮ A new class of hard problem instances for the 0-1 knapsack problem ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Set covering problem with conflict constraints ⋮ Branch-and-cut for linear programs with overlapping SOS1 constraints ⋮ Approximation of the Quadratic Knapsack Problem ⋮ A Fast Large Neighborhood Search for Disjunctively Constrained Knapsack Problems ⋮ Exact algorithms for the bin packing problem with fragile objects ⋮ The maximum flow problem with disjunctive constraints ⋮ An exact algorithm for parallel machine scheduling with conflicts ⋮ A threshold search based memetic algorithm for the disjunctively constrained knapsack problem ⋮ A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Minimum cost flow problem with conflicts ⋮ A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs ⋮ On conflict-free spanning tree: algorithms and complexity ⋮ The knapsack problem with forfeit sets ⋮ Responsive strategic oscillation for solving the disjunctively constrained knapsack problem ⋮ Approximation algorithms for drone delivery scheduling with a fixed number of drones ⋮ A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem ⋮ A unified matheuristic for solving multi-constrained traveling salesman problems with profits ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Paths, trees and matchings under disjunctive constraints ⋮ On the maximum acyclic subgraph problem under disjunctive constraints ⋮ Approximability of the subset sum reconfiguration problem ⋮ A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints ⋮ Approximability of the Subset Sum Reconfiguration Problem ⋮ Scheduling jobs with normally distributed processing times on parallel machines ⋮ Trees in Graphs with Conflict Edges or Forbidden Transitions ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Assignment problem with conflicts ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ Unnamed Item ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ Optimization algorithms for the disjunctively constrained knapsack problem ⋮ Dual Inequalities for Stabilized Column Generation Revisited ⋮ Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width ⋮ Counting and enumerating independent sets with applications to combinatorial optimization problems ⋮ A Fast Algorithm for Knapsack Problem with Conflict Graph ⋮ On the exact separation of cover inequalities of maximum-depth
