JOURNAL ARTICLE

Improved Approximation Algorithms for Bin Packing with Conflicts.

  • Published In: International Journal of Foundations of Computer Science, 2025, v. 36, n. 5. P. 667 1 of 3

  • Database: Academic Search Ultimate 2 of 3

  • Authored By: Huang, Zhihua; Zhang, An; Dósa, György; Chen, Yong; Xiong, Chenling 3 of 3

Abstract

Given a set of items, and a conflict graph defined on the item set, the problem of bin packing with conflicts asks for a partition of items into a minimum number of independent sets so that the total size of items in each independent set does not exceed the bin capacity. As a generalization of both classic bin packing and classic vertex coloring, it is hard to approximate the problem on general graphs. We present new approximation algorithms for bipartite graphs and split graphs. The absolute approximation ratios are shown to be 5 3 and 2 respectively, both improving the existing results. [ABSTRACT FROM AUTHOR]

Additional Information

  • Source:International Journal of Foundations of Computer Science. 2025/08, Vol. 36, Issue 5, p667
  • Document Type:Article
  • Subject Area:Mathematics
  • Publication Date:2025
  • ISSN:0129-0541
  • DOI:10.1142/S0129054122460054
  • Accession Number:186778551
  • Copyright Statement:Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Looking to go deeper into this topic? Look for more articles on EBSCOhost.