Paleosalinity

2013-05-06T11:33:17Z

130.235.100.9:

In [[combinatorial optimization]], a field within mathematics, the '''linear bottleneck assignment problem''' ('''LBAP''') is similar to the [[linear assignment problem]]. <ref>[http://www.assignmentproblems.com/ Assignment Problems], by [[Rainer Burkard]], Mauro Dell'Amico, Silvano Martello, 2009, Chapter 6.2 "[http://books.google.com/books?id=nHIzbApLOr0C&pg=PA198&dq=%22bottleneck+assignment+problem%22&hl=en&ei=A7f0S9DjMYH6sQOYt8CIBQ&sa=X&oi=book_result&ct=result&resnum=2&ved=0CDIQ6AEwAQ#v=onepage&q=%22bottleneck%20assignment%20problem%22&f=false Linear Bottleneck Assignment Problem]" (p. 172)</ref>

In plain words the problem is stated as follows:
:There are a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any task, incurring some ''cost'' that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the ''maximum cost'' among the individual assignments is minimized.

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.

==Formal definition==
The formal definition of the bottleneck assignment problem is

:Given two sets, ''A'' and ''T'', together with a [[weight function]] ''C'' : ''A'' × ''T'' → '''[[real number|R]]'''. Find a [[bijection]] ''f'' : ''A'' → ''T'' such that the [[Loss function|cost function]]:

::<math>\max_{a\in A}C(a,f(a))</math>
:is minimized.

Usually the weight function is viewed as a square real-valued [[matrix (mathematics)|matrix]] ''C'', so that the cost function is written down as:

::<math>\max_{a\in A}C_{a,f(a)}</math>

==Mathematical programming formulation==
:<math> \min \, \max_{i,j} c_{ij}x_{ij}</math>
subject to:
:<math>
\sum^n_{ j = 1} x_{ij} = 1 (i = 1,2,\dots, n),
</math>
:<math>
\sum^n_{ i = 1} x_{ij} = 1 (j = 1,2,\dots, n),
</math>
:<math>
x_{ij} \in \{0,1\} (i, j = 1,2,\dots,n)
</math>

==Asymptotics==
Let <math> c^*_n </math> denote the optimal objective function value for the problem with ''n'' agents and ''n'' tasks. If the costs <math> c_{ij} </math> are sampled from the uniform distribution on (0,1), then <ref> Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," ''Mathematics of Operations Research'', 36 (2): 205-226, 2011. </ref>
:<math> E[c^*_n] = \frac{\log n + \log 2 + \gamma}{n} + O\left(\frac{(\log n)^2}{n^{7/5}}\right)</math>
and
:<math> Var[c_n^*] = \frac{\zeta(2) - 2(\log 2)^2}{n^2} + O\left( \frac{(\log n)^2}{n^{7/3}}\right).</math>

==References==
{{reflist}}

[[Category:Combinatorial optimization]]

formulasearchengine - User contributions [en]

Paleosalinity