Approximating Bin Packing with Conflict Graphs via Maximization Techniques

DOI10.1007/978-3-031-43380-1_19MaRDI QIDQ6496551

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for time constrained scheduling
• An APTAS for bin packing with clique-graph conflicts
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Bin packing can be solved within 1+epsilon in linear time
• A still better performance guarantee for approximate graph coloring
• Geometric algorithms and combinatorial optimization.
• Algorithmic graph theory and perfect graphs
• An approximation scheme for bin packing with conflicts
• Tight Approximation Algorithms for Maximum Separable Assignment Problems
• Linear degree extractors and the inapproximability of max clique and chromatic number
• The Knapsack Problem with Conflict Graphs
• On Bin Packing with Conflicts
• Distributed Approximation Algorithm for Resource Clustering
• A Logarithmic Additive Integrality Gap for Bin Packing
• All-Or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns

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