English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We give a comprehensive study of bin packing with conflicts (BPC). The inputis a set $I$ of items, sizes $s:I \rightarrow [0,1]$, and a conflict graph $G =(I,E)$. The goal is to find a partition of $I$ into a minimum number ofindependent sets, each of total size at most $1$. Being a generalization of thenotoriously hard graph coloring problem, BPC has been studied mostly onpolynomially colorable conflict graphs. An intriguing open question is whetherBPC on such graphs admits the same best known approximation guarantees asclassic bin packing.  We answer this question negatively, by showing that (in contrast to binpacking) there is no asymptotic polynomial-time approximation scheme (APTAS)for BPC already on seemingly easy graph classes, such as bipartite and splitgraphs. We complement this result with improved approximation guarantees forBPC on several prominent graph classes. Most notably, we derive an asymptotic$1.391$-approximation for bipartite graphs, a $2.445$-approximation for perfectgraphs, and a $\left(1+\frac{2}{e}\right)$-approximation for split graphs. Tothis end, we introduce a generic framework relying on a novel interpretation ofBPC allowing us to solve the problem via maximization techniques.  Our framework may find use in tackling BPC on other graph classes arising inapplications.

Approximating Bin Packing with Conflict Graphs via Maximization Techniques