Nos gustaría saber si existen resultados de aproximación conocidos para el corte - mínimo de cardinalidad restringido en los gráficos dirigidos. No pudimos encontrar ningún resultado en la literatura.t
El problema se define de la siguiente manera:
Instancia: Un gráfico dirigido , una función de costo , dos vértices y un entero .w : E → R + 0 s , t ∈ V k
Solución: un corte - , es decir, una partición de en dos conjuntos modo que , y el número de bordes que cruzan el corte es como máximo , es decir, .t V V 1 , V 2 s ∈ V 1 t ∈ V 2 k | { ( u , v ) ∈ E : u ∈ V 1 , v ∈ V 2 } | ≤ k
Medida (para minimizar): El costo del corte:
En " Problemas de cardinalidad restringida y multicriterio (multi) corte ", los autores demuestran que este problema es fuertemente NP-Hard, incluso para gráficos no dirigidos.
Estamos principalmente interesados en algoritmos de aproximación para gráficos dirigidos, pero los resultados de aproximación para el caso no dirigido también pueden ser útiles.
Gracias por cualquier idea.
Respuestas:
Podemos obtener una aproximación de dos criterios de la siguiente manera (o más generalmente aproximación de dos criterios).( 1 + ε , 1 + 1 / ε )(2,2) (1+ε,1+1/ε)
Podemos suponer que sabemos el costo de la solución óptima. Denotalo por . Deje Considere la solución óptima . Entonces w ′ ( u , v ) = w ( u , v )OPT (V1,V2)∑(u,v)∈E( V 1 , V 2 )w′(u,v)=∑(u,v)∈E( V 1 , V 2 )(w(u,v)
Nuestro algoritmo encuentra el corte - dirigido mínimo en con pesos de borde . El costo de este corte es como máximo . Por lo tanto, el corte corta como máximo bordes. El costo del corte es como máximos t (V′1,V′2) G w′ 2 (V′1,V′2)
fuente