Problema de ubicación de la instalación capacitada euclidiana

En el Fondo capacitado Localización de problemas (CFLP) , se nos da un conjunto de clientes y un conjunto de posibles instalaciones F . Cada cliente j ∈ C tiene una demanda d j que debe ser atendida por una o más instalaciones abiertas. Cada instalación i ∈ F tiene un coste de apertura f i y tiene una capacidad u i , que es la demanda máxima de esa instalación i puedo servir. El costo de atender una demanda unitaria del cliente j en la instalación i es c i $C$$F$$j \in C$$d_j$$i \in F$$f_i$$u_i$$i$$j$$i$$c_{ij}$. Queremos abrir un subconjunto de instalaciones y asignar la demanda de los clientes para abrir las instalaciones de manera que se cumplan las demandas de todos los clientes, no se violen las restricciones de capacidad y se minimice el costo total de abrir instalaciones y atender a los clientes. Los costos del servicio son no negativos, simétricos y satisfacen la desigualdad del triángulo.

Arora en [ 1 , página 21] afirma que "Arora, Raghavan y Rao [ 2 ] dan un PTAS para el caso geométrico. Extienden el algoritmo al caso capacitado pero la solución final puede violar las limitaciones de capacidad en una pequeña cantidad". ¿Qué quiere decir con "pequeña cantidad"? Supongo que significa que dan un PTAS que viola las restricciones de capacidad dentro del factor para un arbitrario ϵ > 0 . ¿Es esto correcto?$(1+\epsilon)$$\epsilon > 0$

Cuando busqué en [ 2 ], el único resultado relacionado que encontré fue un algoritmo de tiempo para encontrar una solución aproximada ( 1 + ϵ ) para el problema k -mediano capacitado cuando tienen capacidades uniformes. ¿Arora se refiere al resultado anterior en [ 1 ]?$n^{O(\log^2 (n / \epsilon))}$$(1+\epsilon)$$k$

[ 1 ] S. Arora. Esquemas de aproximación para problemas de optimización geométrica NP-hard: una encuesta. En matemáticas. Programación, Ser. B, vol. 97, pp 43-69, 2003.

[ 2 ] S. Arora, P. Raghavan y S. Rao. Esquemas de aproximación para las medianas k euclidianas y problemas relacionados. En proc. 30 ° Simposio de ACM sobre Teoría de la Computación, pp 106-113, 1998.

Si recuerdo correctamente, debe aproximar el número de clientes conectados a cada puerta. De lo contrario, obtendría inmediatamente algo como , donde g es el número de puertas en un subproblema. Al aproximar este número a un facotr de ( 1 + ε / log n ) en toda la programación dinámica, se puede obtener un error ( 1 + ε ) al final. Eso generaría tiempos de ejecución similares a los que mencionó anteriormente.$O(n^{O(g)})$$g$$(1+\varepsilon/\log n)$$(1+\varepsilon)$