Loading AI tools
From Wikipedia, the free encyclopedia
In combinatorial optimization, a field within mathematics, the linear bottleneck assignment problem (LBAP) is similar to the linear assignment problem.[1]
In plain words the problem is stated as follows:
The term "bottleneck" is explained by a common type of application of the problem, where the cost is the duration of the task performed by an agent. In this setting the "maximum cost" is "maximum duration", which is the bottleneck for the schedule of the overall job, to be minimized.
The formal definition of the bottleneck assignment problem is
Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as:
subject to:
Let denote the optimal objective function value for the problem with n agents and n tasks. If the costs are sampled from the uniform distribution on (0,1), then[2]
and
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.