Improved approximation algorithms for bin packing with conflicts

DOI10.1142/S0129054122460054MaRDI QIDQ6955227zbMATH OpenFDO

Authors Zhihua Huang, An Zhang, György Dósa, Yong Chen, Chenling Xiong

Publication date 23 July 2025

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054122460054

zbMATH Keywords

matchingapproximation algorithmbin packingconflict graph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 3643061 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A branch-and-price algorithm for the bin packing problem with conflicts
• Algorithms for the bin packing problem with conflicts
• 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
• Batched bin packing revisited
• Fibonacci heaps and their uses in improved network optimization algorithms
• Heuristics and lower bounds for the bin packing problem with conflicts
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On Bin Packing with Conflicts
• Precoloring Extension III: Classes of Perfect Graphs
• Precoloring extension on chordal graphs
• Scheduling of a Smart Antenna: Capacitated Coloring of Unit Circular-Arc Graphs
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)

This page was built for publication: Improved approximation algorithms for bin packing with conflicts

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