Problema de asignación de cuello de botella lineal

En optimización combinatoria , un campo dentro de las matemáticas, el problema de asignación de cuello de botella lineal ( LBAP ) es similar al problema de asignación lineal . ^{[ 1 ]}

En pocas palabras, el problema se plantea de la siguiente manera:

Hay varios agentes y varias tareas . Cualquier agente puede ser asignado a cualquier tarea, lo que conlleva un coste que puede variar según la asignación. Es necesario realizar todas las tareas asignando exactamente un agente a cada una, de forma que se minimice el coste máximo entre las asignaciones individuales.

El término " cuello de botella " se explica por un tipo común de aplicación del problema, donde el costo es la duración de la tarea realizada por un agente. En este contexto, el "costo máximo" es la "duración máxima", que constituye el cuello de botella para la programación del trabajo general, el cual debe minimizarse.

La definición formal del problema de asignación de cuello de botella es

Dados dos conjuntos, A y T , junto con una función de peso C  : A × T → R . Hallar una biyección f  : A → T tal que la función de coste :

${\displaystyle \max _{a\in A}C(a,f(a))}$

se minimiza.

Por lo general, la función de ponderación se considera como una matriz cuadrada de valores reales C , de modo que la función de coste se escribe como:

${\displaystyle \max _{a\in A}C_{a,f(a)}}$

${\displaystyle \min \,\max _{i,j}c_{ij}x_{ij}}$

sujeto a:

${\displaystyle \sum _{j=1}^{n}x_{ij}=1(i=1,2,\dots ,n),}$

${\displaystyle \sum _{i=1}^{n}x_{ij}=1(j=1,2,\dots ,n),}$

${\displaystyle x_{ij}\in \{0,1\}(i,j=1,2,\dots ,n)}$

Dejar${\displaystyle c_{n}^{*}}$denota el valor óptimo de la función objetivo para el problema con n agentes y n tareas. Si los costos${\displaystyle c_{ij}}$se muestrean de la distribución uniforme en (0,1), entonces ^{[ 2 ]}

${\displaystyle E[c_{n}^{*}]={\frac {\log n+\log 2+\gamma }{n}}+O\left({\frac {(\log n)^{2}}{n^{7/5}}}\right)}$

y

${\displaystyle Var[c_{n}^{*}]={\frac {\zeta (2)-2(\log 2)^{2}}{n^{2}}}+O\left({\frac {(\log n)^{2}}{n^{7/3}}}\right).}$