✦ LIBER ✦

An asymptotic fully polynomial time approximation scheme for bin covering

✍ Scribed by Klaus Jansen; Roberto Solis-Oba

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 175 KB
Volume: 306
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(03)00363-3

No coin nor oath required. For personal study only.

✦ Synopsis

In the bin covering problem there is a group L = (a1; : : : ; an) of items with sizes s(ai) ∈ (0; 1), and the goal is to ÿnd a packing of the items into bins to maximize the number of bins that receive items of total size at least 1. This is a dual problem to the classical bin packing problem. In this paper we present the ÿrst asymptotic fully polynomial-time approximation scheme for the problem.

📜 SIMILAR VOLUMES

An efficient fully polynomial approximat

An efficient fully polynomial approximation scheme for the Subset-Sum Problem

✍ Hans Kellerer; Renata Mansini; Ulrich Pferschy; Maria Grazia Speranza 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 238 KB

Given a set of n positive integers and a knapsack of capacity c; the Subset-Sum Problem is to find a subset the sum of which is closest to c without exceeding the value c: In this paper we present a fully polynomial approximation scheme which solves the Subset-Sum Problem with accuracy e in time Oðm