Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 285-297 |
Number of pages | 13 |
Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
Volume | 3111 |
Publication status | Published - 1 Dec 2004 |
Externally published | Yes |
ASJC Scopus subject areas
- General Computer Science
- General Biochemistry,Genetics and Molecular Biology
- Theoretical Computer Science