Approximating Bin Packing with Conflict Graphs via Maximization Techniques

DOI10.1007/978-3-031-43380-1_19MaRDI QIDQ6496551zbMATH OpenFDO

Authors Ilan Doron-Arad, Hadas Shachnai

Publication date 3 May 2024

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites work

• scientific article; zbMATH DE number 3643061 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 563208 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A logarithmic additive integrality gap for bin packing
• A still better performance guarantee for approximate graph coloring
• Algorithmic graph theory and perfect graphs
• All-or-nothing generalized assignment with application to scheduling advertising campaigns
• An APTAS for bin packing with clique-graph conflicts
• An approximation scheme for bin packing with conflicts
• Approximation algorithms for time constrained scheduling
• Bin packing can be solved within 1+epsilon in linear time
• Distributed Approximation Algorithm for Resource Clustering
• Geometric algorithms and combinatorial optimization.
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• On Bin Packing with Conflicts
• The Knapsack Problem with Conflict Graphs
• Tight approximation algorithms for maximum separable assignment problems

Cited in

(1)

• Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs

This page was built for publication: Approximating Bin Packing with Conflict Graphs via Maximization Techniques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6496551)