Approximation of knapsack problems with conflict and forcing graphs
From MaRDI portal
Publication:2012887
DOI10.1007/S10878-016-0035-7zbMATH Open1376.90052OpenAlexW2410078569WikidataQ59607346 ScholiaQ59607346MaRDI QIDQ2012887FDOQ2012887
Joachim Schauer, Ulrich Pferschy
Publication date: 3 August 2017
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: http://link.springer.com/10.1007/s10878-016-0035-7
Recommendations
- Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
- The Knapsack Problem with Conflict Graphs
- A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH
- Approximating the quadratic knapsack problem on special graph classes
- A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
Cites Work
- Title not available (Why is that?)
- Decomposition by clique separators
- Modular decomposition and transitive orientation
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Algorithms for the bin packing problem with conflicts
- Title not available (Why is that?)
- Independent Set in P5-Free Graphs in Polynomial Time
- Transitiv orientierbare Graphen
- Listing all potential maximal cliques of a graph
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Treewidth and minimum fill-in: Grouping the minimal separators
- Finding Induced Subgraphs via Minimal Triangulations
- The maximum flow problem with disjunctive constraints
- Title not available (Why is that?)
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Independent Sets of Maximum Weight in Apple-Free Graphs
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Algorithms for weakly triangulated graphs
- Scheduling with conflicts: Online and offline algorithms
- The minimum cost perfect matching problem with conflict pair constraints
- Finding a maximum induced matching in weakly chordal graphs
- The Knapsack Problem with Conflict Graphs
- The minimum spanning tree problem with conflict constraints and its variations
- Paths, trees and matchings under disjunctive constraints
- Maximum weight independent sets in hole- and co-chair-free graphs
- Approximation schemes for a class of subset selection problems
- Improved algorithms for weakly chordal graphs
- Optimizing weakly triangulated graphs
- Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- Title not available (Why is that?)
- An algorithm for the disjunctively constrained knapsack problem
- A Fast Large Neighborhood Search for Disjunctively Constrained Knapsack Problems
Cited In (25)
- Parameterized complexity of conflict-free matchings and paths
- Conflict free version of covering problems on graphs: classical and parameterized
- A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs
- 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 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH
- Fair Packing of Independent Sets
- Exploring the Kernelization Borders for Hitting Cycles
- Combining decomposition approaches for the maximum weight stable set problem
- Title not available (Why is that?)
- Parameterized complexity of conflict-free set cover
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
- Fair allocation algorithms for indivisible items under structured conflict constraints
- A threshold search based memetic algorithm for the disjunctively constrained knapsack problem
- Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games
- The knapsack problem with special neighbor constraints
- Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
- Adaptive feasible and infeasible evolutionary search for the knapsack problem with forfeits
- Approximations for restrictions of the budgeted and generalized maximum coverage problems
- A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
- The knapsack problem with forfeit sets
- Fair allocation of indivisible items with conflict graphs
- Responsive strategic oscillation for solving the disjunctively constrained knapsack problem
- Knapsack: connectedness, path, and shortest-path
This page was built for publication: Approximation of knapsack problems with conflict and forcing graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012887)
