Probablemente sea una pregunta muy estúpida, pero supongamos que tengo dos conjuntos de puntos en el plano $X$ y $Y$ cada uno con cardinalidad $|X| = |Y| = n$ . Para cualquier emparejamiento bipartito $M$ entre $X$ y $Y$ , dejemos que $c_1(M)$ denotan el "coste" total de la concordancia $M$ en la que decimos que el coste entre un par $(x_i,y_j)$ es simplemente la distancia euclidiana entre $x_i$ y $y_j$ . Del mismo modo, dejemos que $c_2(M)$ denotan el coste total del emparejamiento $M$ donde el coste entre un par $(x_i,y_j)$ es el cuadrado de la distancia entre $x_i$ y $y_j$ . Sea $M_1$ y $M_2$ denotan los emparejamientos óptimos con respecto a las funciones de coste $c_1$ y $c_2$ respectivamente. Mi pregunta es: ¿cuáles son los conjuntos de puntos $X$ y $Y$ que maximizan la relación $c_1(M_2)/c_1(M_1)$ ?
Respuesta
¿Demasiados anuncios?
El cociente puede acercarse tanto como queramos a $\sqrt{n}$ .
Empieza poniendo un punto rojo y otro azul de distancia $\sqrt{n}$ aparte (permítanme usar colores en lugar de "punto en $X$ "). A continuación, ponga $n-1$ pares de puntos coincidentes (o muy cercanos si no quieres que coincidan), uno rojo y otro azul, como "peldaños" entre ellos, a una distancia unitaria, pero a lo largo de una gran trayectoria circular.
Con las distancias verdaderas, un par de puntos coincidentes de color opuesto siempre deben coincidir entre sí, por lo que $c_1(M_1)=\sqrt{n}$ . Pero con las distancias al cuadrado, el coste de ese emparejamiento es $n$ de los peldaños y pagar por ellos. $n$ bordes de coste 1 (y estrictamente mejor con una ligera perturbación de los puntos).
Siempre que los escalones estén dispuestos de forma que bajo las distancias cuadradas no se pague ningún atajo, obtenemos $c_1(M_2) = n$ .
Claramente $\sqrt{n}$ es lo mejor que podemos hacer. Si tomamos la distancia $c_1(M_2)$ y lo cortan en $n$ piezas, entonces la suma de los cuadrados de las piezas se minimiza cuando son iguales, por lo tanto $$\frac{c_1(M_2)^2}n\leq c_2(M_2) \leq c_2(M_1)\leq c_1(M_1)^2.$$
