𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A (1–)-approximation algorithm for the generalized assignment problem

✍ Scribed by Zeev Nutov; Israel Beniaminy; Raphael Yuster

Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
173 KB
Volume
34
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

We give a (1-1/e)-approximation algorithm for the max-profit generalized assignment problem (Max-GAP) with fixed profits when the profit (but not necessarily the size) of every item is independent from the bin it is assigned to. The previously best-known approximation ratio for this problem was 1 2 .

📜 SIMILAR VOLUMES

Combinatorial Approximation Algorithms f
Combinatorial Approximation Algorithms for Generalized Flow Problems
✍ Jeffrey D Oldham 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 226 KB

Generalized network flow problems generalize normal network flow problems by specifying a flow multiplier µ v w for each arc v w . For every unit of flow entering the arc, µ v w units of flow exit. We present a strongly polynomial algorithm for a single-source generalized shortest paths problem, usi