Algoritmos para o problema da árvore de Steiner com coleta ...camilam/apresentacao_CamilaMariMatsubara.pdf · Algoritmos para o problema da arvore de Steiner com coleta de pr^emios

Algoritmos para o problema da arvore de

Steiner com coleta de premios

Camila Mari Matsubara

Orientador: Prof. Dr. Jose Coelho de Pina

Defesa de mestrado

Instituto de Matematica e Estatıstica

Universidade de Sao Paulo

Dezembro de 2012

Sumario

Arvore de Steiner

Arvore de Steiner com coleta de premios

Algoritmo de ABHK

Consideracoes finais

Sumario

Arvore de Steiner


Algoritmo de ABHK


Arvore de Steiner

Dados: um grafo e um subconjunto R de vertices terminais.

: R

Arvore de Steiner

Conecta os vertices terminais. Exemplo:

: R

Custo da arvore de Steiner

Dados custos nas arestas, o custo desta arvore de Steiner e

7 + 4 + 2 + 4 + 3 + 5 + 3 = 28.

7

4

2

24

1

3

5

12

3

O problema da arvore de Steiner

Dados:

Grafo G

Custos ce ≥ 0 nas arestas

Subconjunto R de vertices terminais

Objetivo:

Encontrar uma arvore de Steiner T de G com custo mınimo

O problema da arvore de Steiner

Exemplo: arvore com custo mınimo

4 + 2 + 2 + 1 + 3 + 1 + 2 = 15.

7

4

2

24

1

3

5

12

3

Caminho Mınimo

Se |R| = 2 : problema do caminho mınimo.

7

4

2

24

1

3

5

12

3

: R

Arvore Geradora Mınima

Se R = VG : problema da arvore geradora mınima.

7

4

2

24

1

3

5

12

3

: R

Complexidade computacional

Fato: o problema da arvore de Steiner e NP-difıcil.

Reducao polinomial do problema CEd(U,F)

para o problema MinSTd(G , c,R, k)


Exemplo de cobertura exata:

U = {1, 2, 3, 4, 5} e

F = {{1}, {1, 2, 3}, {2, 3}, {4, 5}, {1, 2, 4}, {1, 3, 5}},

a subfamılia {{1}, {2, 3}, {4, 5}} e uma cobertura exata de U


U = {1, 2, 3, 4, 5} e

F = {{1, 2, 3}, {4, 5}, {1, 2, 4}, {1, 3, 5}, {2, 3}, {1}},

n0

1

2

3

4

5

{4, 5}

{1, 3, 5}

{1, 2, 4}

{1, 2, 3}

{2, 3}

{1}

123332

arestas com custo 5

t = |U|k = t + t2


n0

1

2

3

4

5

{4, 5}

{1, 3, 5}

{1, 2, 4}

{1, 2, 3}

{2, 3}

{1}

12

3

3

3

2

arestas com custo 5

t = |U|k = t + t2

Um pouco de historia...

Algoritmos de aproximacao:

2,000 Goemans e Williamson, 1995

1,833 Zelikovsky, 1993

1,746 Berman e Ramaiyer, 1992

1,693 Zelikovsky, 1997

1,667 Promel e Steger, 1997

1,644 Karpinski e Zelikovsky, 1997

1,598 Hougardy, 1999

1,550 Robin e Zelikovsky, 2005

1,390 Byrka, Grandoni, Rothvoss e Sanita, 2010

Programacao linear: Primal

minimize custo da arvore

sob as restricoes corte de todo conjunto ativo

contem uma aresta

A

A = {A : A e ativo}

Programacao linear: Dual

maximize largura das molduras dos conjuntos ativos

sob as restricoes molduras respeitam custos das arestas

Algoritmo MinST-GW

1. Expansao: enquanto ha componente ativo

Incrementar molduras dos componentes ativos ate uma aresta

ficar justa

Adicionar esta aresta a floresta e iniciar outra iteracao

Execucao: MinST-GW

Grafo G :

Execucao: expansao

Execucao: expansao

Execucao: expansao

Execucao: expansao

Execucao: expansao

Execucao: expansao

Execucao: expansao

Execucao: expansao

Execucao: fim da expansao

Algoritmo MinST-GW

2. Poda:

Calcular arvore de Steiner minimal


Execucao: poda

Fator de aproximacao

O algoritmo MinST-GW e uma 2-aproximacao

Sumario

Arvore de Steiner


Algoritmo de ABHK


Custos e penalidades

Dados: um grafo, custos nas arestas e penalidades nos vertices.

7

4

2

24

1

3

5

12

3

42

3

65

4

1

4

2

7

8

O problema da arvore de Steiner com coleta de premios

Dados:

Grafo G

Custos ce ≥ 0 nas arestas

Penalidades πv ≥ 0 nos vertices

Objetivo:

Encontrar uma arvore T de G que minimize custos das

arestas + penalidades dos vertices fora

Custo da arvore de Steiner com coleta de premios

O custo de T e 4+4+3+1+2 + 3+42+5+4 = 68.

7

4

2

24

1

3

5

12

3

42

3

6

5

4

1

4

2

7

8


O custo de T ′ e 4+4+3+1+2+2 + 3+5+4 = 28.

7

4

2

24

1

3

5

12

3

42

3

6

5

4

1

4

2

7

8

Versao com raiz

O custo de Tr e 7+4+2+3+1 + 5+4+4+2 = 32.

7

4

2

24

1

3

5

12

3

42

6

5

4

1

4

2

7

8r


O problema da arvore de Steiner com coleta de premios tambem e

NP-difıcil.

Um pouco de historia...

3 Bienstock, 1993

2− 1n−1 Goemans e Williamson, 1995

2 Johnson, Minkoff e Philips, 2000

2− 2n Feofiloff, Fernandes, Ferreira e Pina, 2007

2−ε Archer, Bateni, Hajiaghayi, Karloff, 2009

Programacao linear: Primal

minimize custo da arvore +

penalidades dos vertices fora da arvore

A

A = {A : A e ativo}

Programacao linear: Dual

maximize largura das molduras dos conjuntos ativos

sob as restricoes molduras respeitam

custos e penalidades

Algoritmo PCST-GW

1. Expansao: enquanto ha pelo menos 2 componentes ativos

Incrementar molduras dos componentes ativos ate:

a. uma aresta ficar justa, ou

b. um componente ficar saturado, ou

c. o complemento de um componente ficar saturado

a. Adicionar a aresta a floresta e iniciar outra iteracao, ou

b. Desativar o componente e iniciar outra iteracao (Z), ou

c. Devolver a arvore induzida por este componente

Execucao: PCST-GW

3

8

79

a

b

c d

9e

Execucao: aresta justa

3

8

79

a

b

c d

9e

Execucao: aresta justa

3

8

79

a

b

c d

9e

Execucao: componente saturado

3

8

79

a

b

c d

9e


3

8

9

a

b

d7

9e

c

Algoritmo PCST-GW

2. Poda: enquanto ha um conjunto S que foi desativado (Z) tal

que |δT (S)| = 1

Remover S da arvore T e iniciar nova iteracao


3

8

9

a

b

d7

9e

c

Execucao: ponte!

3ponte!

8

9

a

b

d7

9e

c

Execucao: poda

3

8

9

a

b

d7

9e

c

Algoritmo com raiz

Penalidade da raiz r = ∞


A arvore T devolvida por R-PCST-GW satisfaz

c(T ) + 2π(T ) ≤ 2 opt

Sumario

Arvore de Steiner


Algoritmo de ABHK


ABHK - Visao geral

O algoritmo R-PCST-GW lida bem quando arvore paga muita

penalidade

Estrategia

Gerar duas arvores TGW e T ST e devolver a mais barata

Primeira candidata

TGW = R-PCST-GW(G , r , c ,12π)

Analise da primeira candidata (0)

TGW = R-PCST-GW(G , r , c ,12π)

T = R-PCST-GW(G , r , c , π)

O = arvore otima da instancia (G , r , c, π)


c(T ) + 2π(T ) ≤ 2 opt

c(TGW ) + 2

(1

2π

)(TGW ) ≤ 2 opt 1

2

c(TGW ) + π(TGW ) ≤ 2 opt 12


c(TGW ) + π(TGW ) ≤ 2 opt 12

≤ 2

(c(O) +

1

2π(O)

)= 2c(O) + π(O)

= 2opt− π(O)


c(TGW ) + π(TGW ) ≤ 2opt− π(O)

δ = π(O)opt

c(TGW ) + π(TGW ) ≤ 2 opt− δopt

= (2−δ) opt

Segunda candidata: intuicao

Mas e se δ < ε?

Ideia ingenua:

Identificar vertices terminais, usando R-PCST-GW

Utilizar um algoritmo para o problema MinST como

caixa-preta

Segunda candidata

Execute R-PCST-Expansao(G , r , c ,βπ) β > 1

Dβ =⋃

S∈Z S

T ST = MinSTρ(G , c ,Dβ)

Analise da segunda candidata

Limitar c(T ST ) e π(T ST )


Demonstra-se que:

c(T ST ) ≤ ρ(1 + (2β − 1)δ) opt

π(Dβ) ≤

(1−δβ

+ δ

)opt


c(T ST ) + π(T ST ) ≤

(ρ(1 + (2β − 1)δ) +

1− δβ

+ δ

)opt


Teorema

Se β = 22−ρ , entao o algoritmo R-PCST-ABHK tem

fator de aproximacao 2− ( 2−ρ2+ρ)2


Finalmente...

A arvore T devolvida por R-PCST-ABHK satisfaz

c(T ) + π(T ) ≤ (2−ε(ρ)) opt

Fatores de aproximacao

MinST ρ Fator de R-PCST-ABHK

Zelikovsky (1993) 1,83 1,9982

Robin e Zelikovsky (2005) 1,55 1,9839

Byrka et al.(2010) 1,39 1,9672

optMinST 1,00 1,8889

Curiosidade

Algoritmo R-PCST-ABHK nao tenta resolver o problema

original.

Sumario

Arvore de Steiner


Algoritmo de ABHK


R-PCST-ABHK × PCST-GW

Comparativo entre os fatores 2−ε e 2− 2n :

MinST ρ 2−ε n >?

Zelikovsky (1993) 1,83 1,9982 1111

Robin e Zelikovsky (2005) 1,55 1,9839 124

Byrka et al.(2010) 1,39 1,9672 60

optMinST 1,00 1,8889 18

Resumindo...

Descricao e analise dos principais algoritmos de aproximacao:

MinST, PCST, R-PCST;

Padronizacao para conceitos, notacao e algoritmos;

Descricao e analise do algoritmo R-PCST-ABHK.

Que interessante...

com ou sem raiz?

prize-collecting;

relaxacao linear importante (conceito de A);

Futuro

(2−ε)-aproximacao sem raiz;

implementacoes;

abordagens diferentes.

Referencias

1 Uma introducao sucinta a algoritmos de aproximacao, 2001

M.Carvalho, M.Cerioli, R.Dahab, P.Feofiloff, C.Fernandes,

C.Ferreira, K.Guimaraes, F.Miyazawa, J.Pina, J.Soares,

Y.Wakabayashi

2 A general approximation technique for constrained forest

problems, 1995

M.Goemans, D.Williamson

Referencias

Primal-dual approximation algorithms for the Prize-Collecting

Steiner Tree Problem, 2007

P.Feofiloff, C. Fernandes, C.Ferreira, J.Pina

Improved approximation algorithms for Prize-Collecting

Steiner Tree and TSP, 2011

A.Archer, M.Bateni, M.Hajiaghayi, H.Karloff

Um exemplo ruim

Para k ≥ 2, um 2k-ciclo + um vertice:

1

1

1

1

1

1

1+z

1+z

1+z

k = 3

Um exemplo ruim

Tα: custo = 2k − 2

1

1

1

1

1

1

1+z

1+z

1+z

custo = 4

Um exemplo ruim

Arvore otima: custo = k(1 + z)

Fator de aproximacao → 2 quando k →∞ e z → 0

1

1

1

1

1

1

1+z

1+z

1+z

custo = 3+3z

Analise da segunda candidata T ST

Limitar separadamente c(T ST ) e π(T ST ).

Analise da segunda candidata π(T ST )

E suficiente limitar π(Dβ).

Vale que

π(Dβ) ≤

(1− δβ

+ δ

)opt

Analise da segunda candidata c(T ST )

Vale que

c(T ST ) ≤ ρ(1 + (2β − 1)δ

Analise da segunda candidata c(T ST )detalhe

Hipotese: Vale lema 5.5

Sejam T , y , LF e Z = R-PCST-Expansao(G , r , c, π).

D = ∪S∈ZS

I qualquer subconjunto de vertices de VG que contem r

A = D \ I = I \ D

Entao existe uma floresta K⊆ T que satisfaz:

1 VK contem todos os vertices em A;

2 Cada arvore na floresta K inclui exatamente um vertice de I ;

3 c(K ) ≤ 2∑

S⊆I yS ≤ 2π(I ) .

Analise da segunda candidata c(T ST )fig1

r

A

D

D

I I

O diagrama ilustra os subconjuntos I e D de VG . As arestas

solidas representam a floresta K .


r

A

D

D

I I

As arestas em linhas pontilhadas conectam vertices em I e as

arestas solidas formam a arvore T .


r

A

D

D

I I

r

A

D

D

I I

(a)

(b)

(a) Na primeira fase, as arestas

de T que conectam dois vertices

de I sao removidas.

(b) Na segunda fase, os conjuntos

pontilhados que foram

desativados durante a execucao

de R-PCST-Expansao e que

nao contem vertices de I sao

removidos.

Documents

Algoritmos para o problema da árvore de Steiner com coleta ...camilam/apresentacao_CamilaMariMatsubara.pdf · Algoritmos para o problema da arvore de Steiner com coleta de pr^emios