๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A note on exact algorithms for the bottleneck generalized assignment problem

โœ Scribed by Silvano Martello; Paolo Toth

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
124 KB
Volume
83
Category
Article
ISSN
0377-2217

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A note on the bottleneck graph partition
A note on the bottleneck graph partition problem
โœ Klinz, Bettina; Woeginger, Gerhard J. ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 47 KB ๐Ÿ‘ 2 views

The bottleneck graph partition problem consists of partitioning the vertices of an undirected edge-weighted graph into two equally sized sets such that the maximum edge weight in the cut separating the two sets becomes minimum. In this short note, we present an optimum algorithm for this problem wit

A (1โ€“)-approximation algorithm for the g
A (1โ€“)-approximation algorithm for the generalized assignment problem
โœ Zeev Nutov; Israel Beniaminy; Raphael Yuster ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 173 KB

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