{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:31:49Z","timestamp":1754152309056,"version":"3.41.2"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"name":"Provincial Universities of Zhejiang","award":["GK229909299001-407"],"award-info":[{"award-number":["GK229909299001-407"]}]},{"name":"Zhejiang Provincial NSF","award":["LY21A010014"],"award-info":[{"award-number":["LY21A010014"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["11971139","11771114"],"award-info":[{"award-number":["11971139","11771114"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Research, Development and Innovation Office - NKFIH","award":["SNN 129364"],"award-info":[{"award-number":["SNN 129364"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:p> 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 [Formula: see text] and [Formula: see text] respectively, both improving the existing results. <\/jats:p>","DOI":"10.1142\/s0129054122460054","type":"journal-article","created":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T01:26:12Z","timestamp":1674609972000},"page":"667-682","source":"Crossref","is-referenced-by-count":3,"title":["Improved Approximation Algorithms for Bin Packing with Conflicts"],"prefix":"10.1142","volume":"36","author":[{"given":"Zhihua","family":"Huang","sequence":"first","affiliation":[{"name":"Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, P. R. China"}]},{"given":"An","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, P. R. China"}]},{"given":"Gy\u00f6rgy","family":"D\u00f3sa","sequence":"additional","affiliation":[{"name":"Pannon University, Egyetem str. 10., Veszpr\u00e9m H-8200, Hungary"}]},{"given":"Yong","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, P. R. China"}]},{"given":"Chenling","family":"Xiong","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2023,1,25]]},"reference":[{"key":"S0129054122460054BIB001","doi-asserted-by":"publisher","DOI":"10.1137\/060666329"},{"key":"S0129054122460054BIB002","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009871302966"},{"key":"S0129054122460054BIB003","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001826"},{"key":"S0129054122460054BIB005","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.2616"},{"key":"S0129054122460054BIB006","first-page":"255","author":"Marx D.","year":"2006","journal-title":"Graph Theory in Paris"},{"key":"S0129054122460054BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.09.007"},{"key":"S0129054122460054BIB008","first-page":"311","volume-title":"Graph Theory and Computing","author":"Foldes S.","year":"1977"},{"key":"S0129054122460054BIB009","first-page":"315","volume-title":"Combinatorial Optimization","author":"Christofides N.","year":"1979"},{"key":"S0129054122460054BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(84)90036-4"},{"key":"S0129054122460054BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-83508-8_21"},{"key":"S0129054122460054BIB012","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"},{"volume-title":"Computers and Intractability","year":"1979","author":"Garey M. R.","key":"S0129054122460054BIB013"},{"key":"S0129054122460054BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/11922377_6"},{"key":"S0129054122460054BIB015","doi-asserted-by":"publisher","DOI":"10.1145\/2843944"},{"key":"S0129054122460054BIB016","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1090.0355"},{"key":"S0129054122460054BIB017","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1100.0406"},{"key":"S0129054122460054BIB018","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1120.0499"},{"key":"S0129054122460054BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(02)00195-8"},{"key":"S0129054122460054BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"S0129054122460054BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-015-0431-3"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122460054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T03:44:02Z","timestamp":1753155842000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122460054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,25]]},"references-count":20,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["10.1142\/S0129054122460054"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122460054","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,1,25]]}}}