The bottleneck problem with minimum quantity commitments

Andrew Lim, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)


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 languageEnglish
Pages (from-to)285-297
Number of pages13
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publication statusPublished - 1 Dec 2004
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Theoretical Computer Science

Cite this