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 consider two well-known natural variants of bin packing, and show thatthese packing problems admit asymptotic fully polynomial time approximationschemes (AFPTAS). In bin packing problems, a set of one-dimensional items ofsize at most 1 is to be assigned (packed) to subsets of sum at most 1 (bins).It has been known for a while that the most basic problem admits an AFPTAS. Inthis paper, we develop methods that allow to extend this result to othervariants of bin packing. Specifically, the problems which we study in thispaper, for which we design asymptotic fully polynomial time approximationschemes, are the following. The first problem is "Bin packing with cardinalityconstraints", where a parameter k is given, such that a bin may contain up to kitems. The goal is to minimize the number of bins used. The second problem is"Bin packing with rejection", where every item has a rejection penaltyassociated with it. An item needs to be either packed to a bin or rejected, andthe goal is to minimize the number of used bins plus the total rejectionpenalty of unpacked items. This resolves the complexity of two importantvariants of the bin packing problem. Our approximation schemes use a novelmethod for packing the small items. This new method is the core of the improvedrunning times of our schemes over the running times of the previous results,which are only asymptotic polynomial time approximation schemes (APTAS).

AFPTAS results for common variants of bin packing: A new method to handle the small items