Given an edge-distance graph of a set of suppliers and clients, the bottleneck problem is to assign each client to a selected supplier minimizing their maximum distance. We introduce minimum quantity commitments to balance workloads of suppliers, provide it a 3-approximation algorithm, and study its generalizations.
|Number of pages||13|
|Journal||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Publication status||Published - 1 Dec 2004|
ASJC Scopus subject areas
- Computer Science(all)
- Biochemistry, Genetics and Molecular Biology(all)
- Theoretical Computer Science