Approximation of knapsack problems with conflict and forcing graphs

DOI10.1007/S10878-016-0035-7MaRDI QIDQ2012887zbMATH OpenOpenAlexWikidataFDO

Authors Ulrich Pferschy, Joachim Schauer

Publication date 3 August 2017

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL http://link.springer.com/10.1007/s10878-016-0035-7

zbMATH Keywords

knapsack problemgraph decompositionplanar graphconflict graphweakly chordal graph

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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

• scientific article; zbMATH DE number 3908479 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 1420907 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A fast large neighborhood search for disjunctively constrained knapsack problems
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Algorithms for the bin packing problem with conflicts
• Algorithms for weakly triangulated graphs
• An algorithm for the disjunctively constrained knapsack problem
• Approximation schemes for a class of subset selection problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Decomposition by clique separators
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• Finding a maximum induced matching in weakly chordal graphs
• Finding induced subgraphs via minimal triangulations
• Improved algorithms for weakly chordal graphs
• Independent set in \(P_5\)-free graphs in polynomial time
• Independent sets of maximum weight in apple-free graphs
• Listing all potential maximal cliques of a graph
• Maximum weight independent sets in hole- and co-chair-free graphs
• Modular decomposition and transitive orientation
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Optimizing weakly triangulated graphs
• Paths, trees and matchings under disjunctive constraints
• Scheduling with conflicts: Online and offline algorithms
• The Knapsack Problem with Conflict Graphs
• The maximum flow problem with disjunctive constraints
• The minimum cost perfect matching problem with conflict pair constraints
• The minimum spanning tree problem with conflict constraints and its variations
• Transitiv orientierbare Graphen
• Treewidth and minimum fill-in: Grouping the minimal separators

Cited in

(29)

• A threshold search based memetic algorithm for the disjunctively constrained knapsack problem
• Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
• The knapsack problem with special neighbor constraints
• Approximations for restrictions of the budgeted and generalized maximum coverage problems
• Combining decomposition approaches for the maximum weight stable set problem
• A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs
• Parameterized complexity of conflict-free matchings and paths
• Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
• Approximating the quadratic knapsack problem on special graph classes
• Knapsack: connectedness, path, and shortest-path
• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• Parameterized complexity of conflict-free matchings and paths
• Exploring the kernelization borders for hitting cycles
• Fair allocation of indivisible items with conflict graphs
• Fair Packing of Independent Sets
• Approximation of the quadratic knapsack problem
• The knapsack problem with neighbour constraints
• Parameterized complexity of conflict-free set cover
• Fair allocation algorithms for indivisible items under structured conflict constraints
• The knapsack problem with forfeit sets
• Responsive strategic oscillation for solving the disjunctively constrained knapsack problem
• Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
• Conflict free version of covering problems on graphs: classical and parameterized
• Counting and enumerating independent sets with applications to combinatorial optimization problems
• A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH
• The Knapsack Problem with Conflict Graphs
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games
• Adaptive feasible and infeasible evolutionary search for the knapsack problem with forfeits

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)