algoritmos de aproximación para el problema de corte de

El Problema Multiway Cut (MC)AA1 combinatorio para el MC

AA2 goloso para el MCAA3 de redondeo para el MC

Otros resultados de AA para el problema MC

Algoritmos de Aproximacion para el problema deCorte de Multicaminos (Multiway Cut)

Julian Viera

Curso de Algoritmos de Aproximacion 2016Facultad de Ingenierıa - IMERL

24 de octubre de 2016

AA para el problema Multiway Cut




Definicion del problema MCAplicaciones del problema MCComplejidad del problema MC

Agenda

1 El Problema Multiway Cut (MC)

2 AA1 combinatorio para el MC

3 AA2 goloso para el MC

4 AA3 de redondeo para el MC

5 Otros resultados de AA para el problema MC






Definicion del problema MC

Se considera un grafo conexo y no dirigido G = (V,E) con

costos positivos asociados a sus aristas c : E → R+

un conjunto de k terminales S = {s1, s2, ..., sk} ⊆ V

El problema Multiway Cut consiste en encontar el conjunto de aristasde E de mınimo costo que al ser removidas desconectan entre sı atodos los k vertices terminales de G.

Es una generalizacion del problema de corte mınimo - flujo maximoentre dos vertices de un grafo.






Ejemplo de instancia del problema MC

(a) Instancia del MC conk = 3

(b) Solucion factible concosto = 14

(c) Solucion optima concosto = 7






Componentes Conexas asociadas a la solucion optima delMC

Al remover las aristas de la solucion optima, el grafo se particionaen exactamente k componentes conexas, con cada una conteniendoun unico vertice terminal.






Aplicaciones del problema Multiway Cut

Minimizacion de costos de comunicacion en sistemas decomputacion paralelos

Asignacion optima de modulos de programa en sistemasmultiprocesador

Particion optima de archivos entre nodos de una red

Particion optima de elementos de un circuito en subcircuitosindependientes






Complejidad del problema Multiway Cut

El problema MC es NP-completo para k ≥ 3

Para k = 2, el problema MC es equivalente al problema dedeterminar el flujo maximo - corte mınimo entre 2 vertices deun grafo, y es resoluble con algoritmos de tiempo polinomico(Ford-Fulkerson)





Descripcion del algoritmoFactor de aproximacion del AA1Ejemplo extremal del AA1

Algoritmo combinatorio AA1 para el Multiway Cut

Corte aislante (isolating cut) de un terminal si : conjunto de aristasde E que al ser removidas desconectan a si del resto de los terminalesde G.

Algoritmo AA1:

1 Para cada i = 1, ..., k determinar el corte aislante de costomınimo del terminal si .

2 Descartar el mas costoso de estos cortes, y devolver la unionde los demas.






AA1 para el MC

1: Sea S = {s1, s2, ..., sk} conjunto de vertices terminales de G2: for i ← 1 to k do3: ti ← contraccion de S \{si}4: Ci ← corte de costo mınimo si − ti5: end for6: Sea c(C1) ≤ c(C2) ≤ ... ≤ c(Ck)

7: return CAA1 =i=k−1⋃i=1

Ci

AA1 fue propuesto por Dahlhaus, Johnson, Papadimitriou, Seymoury Yannakakis en el artıculo “The complexity of multiway cuts”, Sym-posium on the Theory of Computation (STOC) 1992.






Ejemplo del AA1. Paso 1, calculo de cortes mınimos.

Corte aislante C1 de costo mınimo para el terminal s1. c(C1) = 6.






Ejemplo del AA1. Paso 2, union de cortes y descarte.






Teorema : El AA1 tiene factor de aproximacion 2(1− 1k )

A: corte multicaminos optimo de G.Ai , i = 1, ..., k: corte que separa la componente del terminal sien la solucion optima A. Se verifica que A =

⋃i=ki=1 Ai .

Ci , i = 1, ..., k: corte aislante optimo del AA1 para si .

c(C1) ≤ c(A1)c(C2) ≤ c(A2)

...c(Ck) ≤ c(Ak)

k∑i=1

c(Ci ) ≤k∑

i=1

c(Ai ) = 2c(A) = 2OPT

c(CAA1) ≤(

1− 1

k

) k∑i=1

c(Ci ) ≤ 2

(1− 1

k

)OPT QED






Un ejemplo extremal (tight) para el AA1.

Solucion optima del MC : k aristas del anillo ⇒ OPT = k .Solucion del AA1: k-1 aristas colgantes.⇒ c(CAA1) = (2−ε)(k−1) = (2−ε)(1− 1

k )k = (2−ε)(1− 1k )OPT





Descripcion del algoritmoPropiedades del AA2Factor de aproximacion del AA2

Algoritmo goloso AA2 para el Multiway Cut

Algoritmo AA2:

1 Calcular los cortes si − sj de costo mınimo para todos los paresde terminales {si , sj} que aun esten conectados, y remover delgrafo el corte de menor costo, denotado Cij .

2 Repetir el paso 1 hasta que todos los pares de terminales {si , sj}queden desconectados.

3 Devolver CAA2 =⋃Cij .






Ejemplo del AA2

(a) Grafo origen (b) Cortes mınimos entreterminales conectados

(c) Seleccion y remo-cion del corte mınimo demenor costo (C13)






Ejemplo del AA2

(d) Cortes mınimos en-tre terminales conecta-dos

(e) Seleccion y remo-cion del corte mınimode menor costo (C12)

(f) Devolver CAA2 = C12 ∪C13






Propiedades del AA2 goloso

Sea S = {s1, s2, ..., sk} el conjunto de vertices terminales.

1 El AA2 ejecuta exactamente k − 1 pasos. CAA2 =h=k−1⋃h=1

(Cij)h

2 ∀si ∈ S , existe al menos otro terminal sj tal que en algun pasode su ejecucion el AA2 va a elegir el corte Cij .

3 Sean Ci el corte aislante de costo mınimo de si , i = 1, ..., k , yCij cualquiera de los cortes del AA2 que involucra a si . Severifica que c(Cij) ≤ c(Ci )






Grafo de cortes del AA2 goloso

Es el grafo no dirigido Gc obtenido a partir de la aplicacion del AA2,cuyos vertices son los terminales de G y en el que hay arista entredos terminales si y sj si y solo si AA2 elige en alguno de sus pasosel corte Cij .

Propiedad: El grafo de cortes Gc del AA2 es un arbol.

Prueba: por propiedad 2) anterior tiene k vertices de grado mayoro igual a 1. Por propiedad 1) tiene k − 1 aristas =⇒ es un arbol.






Ordenamiento de las aristas del grafo de cortes Gc del AA2

Propiedad: Existe una funcion de mapeo F : S → S tal las aristasde Gc se pueden ordenar como {C1F (1),C2F (2), ...,C(k−1)F (k−1)}Prueba: por construccion de F.

1: Sean S = {s1, s2, ..., sk} y C = CAA2

2: Sea Gc = (S ,C ) el grafo de cortes del AA2

3: while S 6= {sk} do4: for all si/grado(si ) = 1 en Gc y i 6= k do5: Sea j/Cij es la arista de Gc que incide en si =⇒ F (i)← j6: Gc ← Gc\{si}7: end for8: end while






Teorema : El AA2 tiene factor de aproximacion 2(1− 1k )

Prueba:

Ci , i = 1, ..., k: corte aislante optimo del terminal si .

Suponemos sin perdida de generalidad quec(C1) ≤ c(C2) ≤ ... ≤ c(Ck)

CiF (i), i = 1, ..., k − 1: corte del AA2 para si en elordenamiento de aristas de Gc .

c(C1F (1)) ≤ c(C1)c(C2F (2)) ≤ c(C2)

...c(C(k−1)F (k−1)) ≤ c(Ck−1)

c(CAA2) =k−1∑i=1

c(CiF (i)) ≤k−1∑i=1

c(Ci ) = c(CAA1) ≤ 2

(1− 1

k

)OPT





Formulacion como problema de programacion lineal del MCAlgoritmo de redondeo aleatorio para el MCDescripcion del algoritmo AA3Factor de aproximacion del AA3

Modelo de Programacion Lineal Entera para el MC

Las variables del modelo son ”distancias”binarias d entre todo parde nodos del grafo.

mind(u,v)

∑e=(u,v)∈E

c(e)d(u, v)

s.a.

d(u, v) = d(v , u) ≥ 0 ∀u, v ∈ V

d(u, v) ≤ d(u,w) + d(w , v) ∀u, v ∈ V

d(si , sj) = 1 ∀i , j ∈ S , i 6= j

d(u, v) ∈ {0, 1} ∀u, v ∈ V






Modelo Relajado de Programacion Lineal para el MC

Modelo LP

mind(u,v)

∑e=(u,v)∈E

c(e)d(u, v)

s.a.

d(u, v) = d(v , u) ≥ 0 ∀u, v ∈ V

d(u, v) ≤ d(u,w) + d(w , v) ∀u, v ∈ V

d(si , sj) = 1 ∀i , j ∈ S , i 6= j

0 ≤ d(u, v) ≤ 1 ∀u, v ∈ V

Gap de integralidad de la relajacion LP

Puede probarse que esta relajacion LP para el MC tiene un gap deintegralidad de valor 2(1− 1

k ).






Un algoritmo de redondeo aleatorio para el Multiway Cut

Algoritmo de redondeo aleatorio para el MC:1 Resolver el problema relajado LP para obtener una solucion del

MC optima fraccionaria.2 Sortear aleatoriamente un valor de ρ en el intervalo

[0, 1

2

].

3 Elegir para la solucion toda arista (u, v) ∈ E / ∃ terminal s cond(u, s) ≤ ρ ≤ d(v , s).






Valor esperado del algoritmo aleatorio para el MC

Propiedad: ∀(u, v) ∈ E , la probabilidad de esa arista se elegida porel algoritmo aleatorio esta acotada por 2d(u, v)

Prueba (para un terminal dado s):P{se elige (u, v)} ≤ 2(d(v , s)− d(u, s)) por tener ρ distribucionuniforme de densidad 2.d(v , s)− d(u, s) ≤ d(u, v) por cumplir d la desigualdad triangular.=⇒ P{se elige (u, v)} ≤ 2d(u, v)

Teorema: El valor esperado del costo del corte Caleat elegidoesta acotado por 2OPTf

Prueba:E [c(Caleat)] =

∑e∈E

c(e)P{e} ≤∑

e=(u,v)∈E

c(e)2d(u, v) = 2OPTf






Algoritmo de redondeo AA3 para el Multiway Cut1 Resolver el problema relajado LP para obtener una solucion del

MC optima fraccionaria.2 Para cada terminal si , i = 1, ..., k elegir ρi en el intervalo

(0, 1

2

)de forma de minimizar el costo de las aristas que atraviesan lafrontera de la bola Bd(si , ρi ). Estas aristas forman un corteaislante Ci para si .

3 Descartar el mas costoso de estos cortes, y devolver la unionde los (k − 1) cortes restantes.






Teorema: El AA3 tiene factor de aproximacion 2(1− 1k )

Prueba:

Ci : corte de costo mınimo del AA3 para el terminal si .

C =i=k⋃i=1

Ci : solucion del AA3 sin descartar el corte mas

costoso.

CAA3 : corte solucion del AA3.

Caleat : corte solucion del algoritmo aleatorio.

c(C) =k∑

i=1

c(Ci ) ≤ mınρ

c(Caleat) ≤ E [c(Caleat)] ≤ 2OPTf

c(CAA3) ≤(

1− 1

k

)c(C) ≤ 2

(1− 1

k

)OPTf QED





AA con mejores factores para el MCUn resultado de inaproximabilidad para el MC

AA con mejores factores para el MC

Algoritmo de factor 32 −

1k de Callinescu, Karloff y Rabani.

Presentan la relajacion CKR en el artıculo “An improvedApproximation Algorithm for Multiway Cut”, ACMSymposium on the Theory of Computation 1998, pp 48-52.

Algoritmo de factor 1,3438 de Karger, Klein, Stein, Thorup yYoung. Presentado en el artıculo “Rounding Algorithms for aGeometric Embedding of Minimum Multiway Cut”, JournalMathematics of Operations Research 29, 2004.

Algoritmo de factor 1,2965 de Sharma y Vondrak. Presentadoen el artıculo “Multiway Cuts, Pairwise RealizableDistributions and Descending Thresholds”, 2014.






Un resultado de inaproximabilidad para el MC

Gap de Integralidad del Multiway Cut para la relajacion CKR

Freund y Karloff probaron en 2000 que MC tiene un gap deintegralidad de 8

7+ 1k−1

∀k ≥ 3, para la relajacion CKR.

UG-hardness

Manokaran et al. demostraron en 2008 que si la conjetura UGC(Unique Games Conjecture) es verdadera, es NP-hard hallar unfactor de aproximacion para el MC mejor que el gap de integralidadde la relajacion CKR =⇒ la UG-hardness de MC es 8

7 − ε ' 1,1428.






FIN

Muchas gracias.


algoritmos de aproximación para el problema de corte de

Documents