Problema de asignación

En el problema de asignación equilibrada, ambas partes del grafo bipartito tienen el mismo número de vértices, denotado por n .

Uno de los primeros algoritmos de tiempo polinomial para la asignación equilibrada fue el algoritmo húngaro . Es un algoritmo global  : se basa en mejorar un emparejamiento a lo largo de caminos de aumento (caminos alternos entre vértices no emparejados). Su complejidad de tiempo de ejecución, cuando se utilizan montones de Fibonacci , es${\displaystyle O(mn+n^{2}\log n)}$, ^{[ 2 ]} donde m es el número de aristas. Este es actualmente el tiempo de ejecución más rápido de un algoritmo fuertemente polinomial para este problema. Algunas variantes del algoritmo húngaro también se benefician de la computación paralela , incluida la aceleración por GPU. ^{[ 3 ]} Si todos los pesos son enteros, entonces el tiempo de ejecución se puede mejorar a ${\displaystyle O(mn+n^{2}\log \log n)}$, pero el algoritmo resultante es solo débilmente polinomial . ^{[ 4 ]} Si los pesos son enteros y todos los pesos son como máximo C (donde C >1 es algún entero), entonces el problema se puede resolver en${\displaystyle O(m{\sqrt {n}}\log(n\cdot C))}$tiempo débilmente polinomial en un método llamado escalado de peso . ^{[ 5 ] [ 6 ] [ 7 ]}

Además de los métodos globales, existen métodos locales que se basan en encontrar actualizaciones locales (en lugar de rutas de aumento completas). Estos métodos tienen peores garantías de tiempo de ejecución asintótico, pero a menudo funcionan mejor en la práctica. Estos algoritmos se denominan algoritmos de subasta , algoritmos de reetiquetado o algoritmos de preflujo. Se ha demostrado que algunos de estos algoritmos son equivalentes. ^{[ 8 ]}

Algunos de los métodos locales asumen que el grafo admite un emparejamiento perfecto ; si este no es el caso, algunos de estos métodos podrían ejecutarse indefinidamente. ^{[ 1 ] : 3} Una forma técnica sencilla de resolver este problema es extender el grafo de entrada a un grafo bipartito completo, agregando aristas artificiales con pesos muy grandes. Estos pesos deben exceder los pesos de todos los emparejamientos existentes, para evitar la aparición de aristas artificiales en la posible solución.

Como demostraron Mulmuley, Vazirani y Vazirani, ^{[ 9 ]} el problema del emparejamiento perfecto de peso mínimo se convierte en encontrar menores en la matriz de adyacencia de un grafo. Usando el lema de aislamiento , se puede encontrar un emparejamiento perfecto de peso mínimo en un grafo con una probabilidad de al menos 1/2 . Para un grafo con n vértices, se requiere${\displaystyle O(\log ^{2}(n))}$tiempo.

En el problema de asignación desequilibrada, la parte mayor del grafo bipartito tiene n vértices y la parte menor tiene r < n vértices. También hay una constante s que es como máximo la cardinalidad de un emparejamiento máximo en el grafo. El objetivo es encontrar un emparejamiento de costo mínimo de tamaño exactamente s . El caso más común es aquel en el que el grafo admite un emparejamiento unilateral perfecto (es decir, un emparejamiento de tamaño r ), y s = r .

Una asignación desequilibrada se puede reducir a una asignación equilibrada. La reducción ingenua consiste en añadir${\displaystyle nr}$nuevos vértices a la parte más pequeña y conectarlos a la parte más grande usando aristas de costo 0. Sin embargo, esto requiere${\displaystyle n(nr)}$nuevos bordes. Una reducción más eficiente se llama técnica de duplicación . Aquí, un nuevo grafo G'Se construye a partir de dos copias del grafo original G : una copia hacia adelante Gf y una copia hacia atrás Gb. La copia hacia atrás se "invierte", de modo que, en cada lado de G' , ahora hay n + r vértices. Entre las copias, necesitamos agregar dos tipos de aristas de enlace: ^{[ 1 ] : 4–6}

• De grande a grande: desde cada vértice en la parte más grande de Gf , agregue una arista de costo cero al vértice correspondiente en Gb .
• De pequeño a pequeño: si el grafo original no tiene un emparejamiento unilateral perfecto, entonces desde cada vértice en la parte más pequeña de Gf , agregue una arista de costo muy alto al vértice correspondiente en Gb .

En general, como máximo${\displaystyle n+r}$Se requieren nuevos bordes. El grafo resultante siempre tiene una coincidencia de tamaño perfecta.${\displaystyle n+r}$. Un emparejamiento perfecto de costo mínimo en este grafo debe consistir en emparejamientos de cardinalidad máxima de costo mínimo en Gf y Gb. El principal problema con esta técnica de duplicación es que no hay ganancia de velocidad cuando${\displaystyle r\ll n}$.

En lugar de utilizar la reducción, el problema de asignación desequilibrada se puede resolver generalizando directamente los algoritmos existentes para la asignación equilibrada. El algoritmo húngaro se puede generalizar para resolver el problema en${\displaystyle O(ms+s^{2}\log r)}$tiempo fuertemente polinomial. En particular, si s = r, entonces el tiempo de ejecución es${\displaystyle O(mr+r^{2}\log r)}$. Si los pesos son enteros, entonces el método de Thorup se puede utilizar para obtener un tiempo de ejecución de${\displaystyle O(ms+s^{2}\log \log r)}$. ^{[ 1 ] : 6}

El problema de asignación se puede resolver presentándolo como un programa lineal . Para mayor comodidad, presentaremos el problema de maximización. Cada arista ( i , j ) , donde i está en A y j está en T, tiene un peso.${\textstyle w_{ij}}$. Para cada arista${\displaystyle (i,j)}$Tenemos una variable${\textstyle x_{ij}}$_{La variable es} 1 si la arista está contenida en la coincidencia y 0 en caso contrario, por lo que establecemos las restricciones del dominio: $${\displaystyle 0\leq x_{ij}\leq 1{\text{ para }}i,j\in A,T,\,}$$$${\displaystyle x_{ij}\in \mathbb {Z} {\text{ para }}i,j\in A,T.}$$

El peso total del emparejamiento es:${\displaystyle \sum _{(i,j)\in A\times T}w_{ij}x_{ij}}$El objetivo es encontrar la pareja perfecta de peso máximo.

Para garantizar que las variables representen realmente una correspondencia perfecta, agregamos restricciones que dicen que cada vértice es adyacente a exactamente una arista en la correspondencia, es decir, $${\displaystyle {\begin{aligned}\sum _{j\in T}x_{ij}&=1{\text{ para }}i\in A\\\sum _{i\in A}x_{ij}&=1{\text{ para }}j\in T\end{aligned}}}$$

En resumen, tenemos el siguiente LP:

$${\displaystyle {\begin{aligned}{\text{maximizar}}&\sum _{(i,j)\in A\times T}w_{ij}x_{ij}\\{\text{sujeto a}}&\sum _{j\in T}x_{ij}=1{\text{ para }}i\in A,\,\sum _{i\in A}x_{ij}=1{\text{ para }}j\in T\\&0\leq x_{ij}\leq 1{\text{ para }}i,j\in A,T\\&x_{ij}\in \mathbb {Z} {\text{ para }}i,j\in A,T\end{aligned}}}$$ Se trata de un programa lineal entero. Sin embargo, podemos resolverlo sin las restricciones de integralidad (es decir, eliminando la última restricción), utilizando métodos estándar para la resolución de programas lineales continuos. Si bien esta formulación también permite valores fraccionarios para las variables, en este caso particular, el programa lineal siempre tiene una solución óptima cuando las variables toman valores enteros. Esto se debe a que la matriz de restricciones del programa lineal fraccionario es totalmente unimodular  , es decir, satisface las cuatro condiciones de Hoffman y Gale.

Existen otros enfoques para el problema de asignación, los cuales son revisados ​​por Duan y Pettie ^{[ 10 ]} (véase la Tabla II). Su trabajo propone un algoritmo de aproximación para el problema de asignación (y el problema más general de emparejamiento de peso máximo ), que se ejecuta en tiempo lineal para cualquier límite de error fijo.