Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementações do Método de AproximaçãoPrimal-Dual
aplicado ao Problema da Floresta de Steiner
Rafael Pereira Luna
Departamento de Ciência da ComputaçãoInstituto de Matemática e Estatística
Universidade de São Paulo
27 de abril de 2006
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Visão Geral
1 O Problema da Floresta de Steiner
2 Algoritmo de Goemans e WilliamsonAlguns conceitos importantesO algoritmo
3 Implementações do Algoritmo
4 Considerações Finais
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Visão Geral
1 O Problema da Floresta de Steiner
2 Algoritmo de Goemans e WilliamsonAlguns conceitos importantesO algoritmo
3 Implementações do Algoritmo
4 Considerações Finais
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Definição do Problema
Dados: G = (V , E), uma função custo c : E → Q> e umafamília R de subconjuntos de V ,
Encontrar: R-floresta F que minimize c(F ).
Definição de R-floresta
Uma R-floresta F é uma floresta geradora de G tq cadaconjunto de R está contido em alguma componente de F .
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Definição do Problema
Dados: G = (V , E), uma função custo c : E → Q> e umafamília R de subconjuntos de V ,
Encontrar: R-floresta F que minimize c(F ).
Definição de R-floresta
Uma R-floresta F é uma floresta geradora de G tq cadaconjunto de R está contido em alguma componente de F .
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Definição do Problema
Dados: G = (V , E), uma função custo c : E → Q> e umafamília R de subconjuntos de V ,
Encontrar: R-floresta F que minimize c(F ).
Definição de R-floresta
Uma R-floresta F é uma floresta geradora de G tq cadaconjunto de R está contido em alguma componente de F .
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Exemplo
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Exemplo
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Nomenclatura
vértices de Steiner : vértices que não estão em conjuntosda família R;
terminais : vértices que estão em algum conjunto de R;
conjunto de terminais : cada um dos conjuntos de R;
floresta de Steiner : R-floresta quando R está implícito.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Nomenclatura
vértices de Steiner : vértices que não estão em conjuntosda família R;
terminais : vértices que estão em algum conjunto de R;
conjunto de terminais : cada um dos conjuntos de R;
floresta de Steiner : R-floresta quando R está implícito.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Nomenclatura
vértices de Steiner : vértices que não estão em conjuntosda família R;
terminais : vértices que estão em algum conjunto de R;
conjunto de terminais : cada um dos conjuntos de R;
floresta de Steiner : R-floresta quando R está implícito.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Nomenclatura
vértices de Steiner : vértices que não estão em conjuntosda família R;
terminais : vértices que estão em algum conjunto de R;
conjunto de terminais : cada um dos conjuntos de R;
floresta de Steiner : R-floresta quando R está implícito.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Aplicações
Projeto de redes;
Roteamento de circuitos VLSI.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Complexidade
O Problema de Steiner em Grafos , que éNP-difícil [Karp72], é um caso particular do Problema daFloresta de Steiner (|R| = 1);
O Problema da Floresta de Steiner é MAX SNP-difícil;
Primeiro algoritmo de aproximação para o Problema daFloresta de Steiner: (2− 2
t )-aproximação projetada porAgrawal, Klein e Ravi [AGW91].
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Complexidade
O Problema de Steiner em Grafos , que éNP-difícil [Karp72], é um caso particular do Problema daFloresta de Steiner (|R| = 1);
O Problema da Floresta de Steiner é MAX SNP-difícil;
Primeiro algoritmo de aproximação para o Problema daFloresta de Steiner: (2− 2
t )-aproximação projetada porAgrawal, Klein e Ravi [AGW91].
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Complexidade
O Problema de Steiner em Grafos , que éNP-difícil [Karp72], é um caso particular do Problema daFloresta de Steiner (|R| = 1);
O Problema da Floresta de Steiner é MAX SNP-difícil;
Primeiro algoritmo de aproximação para o Problema daFloresta de Steiner: (2− 2
t )-aproximação projetada porAgrawal, Klein e Ravi [AGW91].
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Visão Geral
1 O Problema da Floresta de Steiner
2 Algoritmo de Goemans e WilliamsonAlguns conceitos importantesO algoritmo
3 Implementações do Algoritmo
4 Considerações Finais
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Algoritmo de Goemans e Williamson (92)
Goemans e Williamson generalizaram o algoritmo deAgrawal, Klein e Ravi e projetaram um algoritmo deaproximação primal-dual que se aplica a uma amplaclasse de problemas de projeto de redes;
Este algoritmo é uma (2− 2t )-aproximação para o Problema
da Floresta de Steiner;
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Algoritmo de Goemans e Williamson (92)
Goemans e Williamson generalizaram o algoritmo deAgrawal, Klein e Ravi e projetaram um algoritmo deaproximação primal-dual que se aplica a uma amplaclasse de problemas de projeto de redes;
Este algoritmo é uma (2− 2t )-aproximação para o Problema
da Floresta de Steiner;
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Visão Geral
1 O Problema da Floresta de Steiner
2 Algoritmo de Goemans e WilliamsonAlguns conceitos importantesO algoritmo
3 Implementações do Algoritmo
4 Considerações Finais
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Conjunto ativo: S ⊂ V é ativo se existe algum T ∈ R tal queS ∩ T 6= ∅ e T \ S 6= ∅.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Conjunto ativo: S ⊂ V é ativo se existe algum T ∈ R tal queS ∩ T 6= ∅ e T \ S 6= ∅.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Componente ativa: componente cujo conjunto devértices é ativo;
Componente inativa: componente cujo conjunto devértices não é ativo.
Observação importante
Se F é uma floresta geradora que não tem componentesativas , então F é uma floresta de Steiner .
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Componente ativa: componente cujo conjunto devértices é ativo;
Componente inativa: componente cujo conjunto devértices não é ativo.
Observação importante
Se F é uma floresta geradora que não tem componentesativas , então F é uma floresta de Steiner .
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Visão Geral
1 O Problema da Floresta de Steiner
2 Algoritmo de Goemans e WilliamsonAlguns conceitos importantesO algoritmo
3 Implementações do Algoritmo
4 Considerações Finais
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Esboço 1
F ← (V , ∅);Fase iterativa: enquanto F contém componentesativas faça
escolha uma aresta externa boa e que possui pelo menosum extremo em uma componente ativa;EF ← EF ∪ {e}.
Fase da limpeza: encontra floresta de Steiner minimalem F .
Como escolher uma aresta boa?
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Esboço 1
F ← (V , ∅);Fase iterativa: enquanto F contém componentesativas faça
escolha uma aresta externa boa e que possui pelo menosum extremo em uma componente ativa;EF ← EF ∪ {e}.
Fase da limpeza: encontra floresta de Steiner minimalem F .
Como escolher uma aresta boa?
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Esboço 1
F ← (V , ∅);Fase iterativa: enquanto F contém componentesativas faça
escolha uma aresta externa boa e que possui pelo menosum extremo em uma componente ativa;EF ← EF ∪ {e}.
Fase da limpeza: encontra floresta de Steiner minimalem F .
Como escolher uma aresta boa?
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Esboço 1
F ← (V , ∅);Fase iterativa: enquanto F contém componentesativas faça
escolha uma aresta externa boa e que possui pelo menosum extremo em uma componente ativa;EF ← EF ∪ {e}.
Fase da limpeza: encontra floresta de Steiner minimalem F .
Como escolher uma aresta boa?
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Formulação do Problema da Floresta de Steineratravés de um programa inteiro
Observação importante
Se F é uma floresta de Steiner, então, para todo S ativo,EF ∩ δ(S) 6= ∅.
Programa inteiro equivalente ao Problema daFloresta de Steiner
minimize∑
e∈E cexe
sob as restrições∑
e∈δ(S) xe ≥ 1 para cada S ativo,xe ∈ {0, 1} para cada e em E .
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Formulação do Problema da Floresta de Steineratravés de um programa inteiro
Observação importante
Se F é uma floresta de Steiner, então, para todo S ativo,EF ∩ δ(S) 6= ∅.
Programa inteiro equivalente ao Problema daFloresta de Steiner
minimize∑
e∈E cexe
sob as restrições∑
e∈δ(S) xe ≥ 1 para cada S ativo,xe ∈ {0, 1} para cada e em E .
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Relaxação linear e dual
Relaxação linear
minimize∑
e∈E cexe
sob as restrições∑
e∈δ(S) xe ≥ 1 para cada S ativo,xe ≥ 0 para cada e em E .
Dual
maximize∑
S ativo ySsob as restrições
∑S ativo:e∈δ(S) yS ≤ ce para cada e em E ,
yS ≥ 0 para cada S ativo.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Relaxação linear e dual
Relaxação linear
minimize∑
e∈E cexe
sob as restrições∑
e∈δ(S) xe ≥ 1 para cada S ativo,xe ≥ 0 para cada e em E .
Dual
maximize∑
S ativo ySsob as restrições
∑S ativo:e∈δ(S) yS ≤ ce para cada e em E ,
yS ≥ 0 para cada S ativo.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Esboço 2
F ← (V , ∅);yS ← 0 para cada S ativo; B y dual viávelFase iterativa: enquanto F contém componentesativas faça
calcule ε máximo;yS ← yS + ε para cada S ativo;e← aresta externa a F tq
∑S ativo:e∈δ(S) yS = c e;
EF ← EF ∪ {e}.Fase da limpeza: encontra floresta de Steiner minimalem F .
Como calcular ε?
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Esboço 2
F ← (V , ∅);yS ← 0 para cada S ativo; B y dual viávelFase iterativa: enquanto F contém componentesativas faça
calcule ε máximo;yS ← yS + ε para cada S ativo;e← aresta externa a F tq
∑S ativo:e∈δ(S) yS = c e;
EF ← EF ∪ {e}.Fase da limpeza: encontra floresta de Steiner minimalem F .
Como calcular ε?
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Esboço 2
F ← (V , ∅);yS ← 0 para cada S ativo; B y dual viávelFase iterativa: enquanto F contém componentesativas faça
calcule ε máximo;yS ← yS + ε para cada S ativo;e← aresta externa a F tq
∑S ativo:e∈δ(S) yS = c e;
EF ← EF ∪ {e}.Fase da limpeza: encontra floresta de Steiner minimalem F .
Como calcular ε?
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Esboço 2
F ← (V , ∅);yS ← 0 para cada S ativo; B y dual viávelFase iterativa: enquanto F contém componentesativas faça
calcule ε máximo;yS ← yS + ε para cada S ativo;e← aresta externa a F tq
∑S ativo:e∈δ(S) yS = c e;
EF ← EF ∪ {e}.Fase da limpeza: encontra floresta de Steiner minimalem F .
Como calcular ε?
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Cálculo do ε
Para cada aresta externa uv , calcular folga(uv), o valor doincremento necessário para que
∑S ativo:uv∈δ(S) yS = cuv :
(cuv −∑
S:uv∈δ(S) yS)/2, se u e v pertencem acomponentes ativas;
cuv −∑
S:uv∈δ(S) yS, se u ou v , mas não ambos, pertencea uma componente ativa;
∞, se u e v pertencem a componentes inativas.
Cálculo de ε
ε = min{folga(e) | e é uma aresta externa aF}
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Cálculo do ε
Para cada aresta externa uv , calcular folga(uv), o valor doincremento necessário para que
∑S ativo:uv∈δ(S) yS = cuv :
(cuv −∑
S:uv∈δ(S) yS)/2, se u e v pertencem acomponentes ativas;
cuv −∑
S:uv∈δ(S) yS, se u ou v , mas não ambos, pertencea uma componente ativa;
∞, se u e v pertencem a componentes inativas.
Cálculo de ε
ε = min{folga(e) | e é uma aresta externa aF}
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Cálculo do ε
Para cada aresta externa uv , calcular folga(uv), o valor doincremento necessário para que
∑S ativo:uv∈δ(S) yS = cuv :
(cuv −∑
S:uv∈δ(S) yS)/2, se u e v pertencem acomponentes ativas;
cuv −∑
S:uv∈δ(S) yS, se u ou v , mas não ambos, pertencea uma componente ativa;
∞, se u e v pertencem a componentes inativas.
Cálculo de ε
ε = min{folga(e) | e é uma aresta externa aF}
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Cálculo do ε
Para cada aresta externa uv , calcular folga(uv), o valor doincremento necessário para que
∑S ativo:uv∈δ(S) yS = cuv :
(cuv −∑
S:uv∈δ(S) yS)/2, se u e v pertencem acomponentes ativas;
cuv −∑
S:uv∈δ(S) yS, se u ou v , mas não ambos, pertencea uma componente ativa;
∞, se u e v pertencem a componentes inativas.
Cálculo de ε
ε = min{folga(e) | e é uma aresta externa aF}
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Cálculo do ε
Para cada aresta externa uv , calcular folga(uv), o valor doincremento necessário para que
∑S ativo:uv∈δ(S) yS = cuv :
(cuv −∑
S:uv∈δ(S) yS)/2, se u e v pertencem acomponentes ativas;
cuv −∑
S:uv∈δ(S) yS, se u ou v , mas não ambos, pertencea uma componente ativa;
∞, se u e v pertencem a componentes inativas.
Cálculo de ε
ε = min{folga(e) | e é uma aresta externa aF}
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Alguns conceitos importantesO algoritmo
Algoritmo MinFS-GW(G,R, c)
1 F ← (VG, ∅)2 Eext← EG3 yS ← 0 para cadaconjuntoS ativo4 enquantoF tem alguma componente ativafaça5 escolhae tal quefolga(e) = min{folga(e) | e ∈ Eext}6 sefolga(e) =∞7 pare: “o problema não tem solução!”8 yS ← yS + folga(e) para cadacomponente ativaS deF9 EF ← EF ∪ {e}
10 Eext← Eext \ {uv | u ev estão na mesma componente emF}11 sejaF ′ umaR-floresta minimal contida emF12 devolvaF ′
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Visão Geral
1 O Problema da Floresta de Steiner
2 Algoritmo de Goemans e WilliamsonAlguns conceitos importantesO algoritmo
3 Implementações do Algoritmo
4 Considerações Finais
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementações estudadas
Goemans e Williamson [GW92]: O(n2 log n)
Gabow, Goemans e Williamson [GGW93]:O(n(n +
√m log log n));
Klein [Klein94]: O(√
m log n);
Cole, Hariharan, Lewenstein e Porat [CHLP01]:O(k(m + n) log2 n).
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementações estudadas
Goemans e Williamson [GW92]: O(n2 log n)
Gabow, Goemans e Williamson [GGW93]:O(n(n +
√m log log n));
Klein [Klein94]: O(√
m log n);
Cole, Hariharan, Lewenstein e Porat [CHLP01]:O(k(m + n) log2 n).
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementações estudadas
Goemans e Williamson [GW92]: O(n2 log n)
Gabow, Goemans e Williamson [GGW93]:O(n(n +
√m log log n));
Klein [Klein94]: O(√
m log n);
Cole, Hariharan, Lewenstein e Porat [CHLP01]:O(k(m + n) log2 n).
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementações estudadas
Goemans e Williamson [GW92]: O(n2 log n)
Gabow, Goemans e Williamson [GGW93]:O(n(n +
√m log log n));
Klein [Klein94]: O(√
m log n);
Cole, Hariharan, Lewenstein e Porat [CHLP01]:O(k(m + n) log2 n).
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Características comuns
y não é armazenado explicitamente;
as arestas externas são mantidas em heaps de mínimo;
conjunto de vértices das componentes da floresta:union-find.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Características comuns
y não é armazenado explicitamente;
as arestas externas são mantidas em heaps de mínimo;
conjunto de vértices das componentes da floresta:union-find.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Características comuns
y não é armazenado explicitamente;
as arestas externas são mantidas em heaps de mínimo;
conjunto de vértices das componentes da floresta:union-find.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Questão importante
Como manter atualizada de maneira eficiente a informaçãoque indica o número de extremos de uma aresta que estãoem componentes ativas?
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de GW
Apenas uma aresta externa é considerada para cada par decomponentes.
guardar estas arestas em um heap de mínimo;
chave de cada aresta no heap: folga.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de GW
Apenas uma aresta externa é considerada para cada par decomponentes.
guardar estas arestas em um heap de mínimo;
chave de cada aresta no heap: folga.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de GGW
Idéia
Reduzir o número de arestas armazenadas.
Organizar as arestas em heaps menores.
fase iterativa dividida em subfases de no máximo riterações (r =
√m/ log log n);
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de GGW
Idéia
Reduzir o número de arestas armazenadas.
Organizar as arestas em heaps menores.
fase iterativa dividida em subfases de no máximo riterações (r =
√m/ log log n);
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de GGW (continuação)
em cada subfase, são consideradas apenas as 2r“menores” arestas incidentes em cada componente;
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de GGW (continuação)
arestas são mantidas em pacotes com capacidademáxima log n.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de Klein
IdéiaAtribuir de modo adequado as arestas externas aos seusextremos.
para cada componente S e para cada bicategoria b, umheap h(S, b) guarda as arestas externas de b atribuídasa S;
bicategorias: (ATIVO, ATIVO), (ATIVO, INATIVO),(INATIVO, ATIVO) e (INATIVO, INATIVO);
os heaps h(∗, b) são mantidos em um heap H(b);
arestas não atribuídas a S são mantidas em uma listaligada extra(S).
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de Klein
IdéiaAtribuir de modo adequado as arestas externas aos seusextremos.
para cada componente S e para cada bicategoria b, umheap h(S, b) guarda as arestas externas de b atribuídasa S;
bicategorias: (ATIVO, ATIVO), (ATIVO, INATIVO),(INATIVO, ATIVO) e (INATIVO, INATIVO);
os heaps h(∗, b) são mantidos em um heap H(b);
arestas não atribuídas a S são mantidas em uma listaligada extra(S).
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de Klein
IdéiaAtribuir de modo adequado as arestas externas aos seusextremos.
para cada componente S e para cada bicategoria b, umheap h(S, b) guarda as arestas externas de b atribuídasa S;
bicategorias: (ATIVO, ATIVO), (ATIVO, INATIVO),(INATIVO, ATIVO) e (INATIVO, INATIVO);
os heaps h(∗, b) são mantidos em um heap H(b);
arestas não atribuídas a S são mantidas em uma listaligada extra(S).
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de Klein
IdéiaAtribuir de modo adequado as arestas externas aos seusextremos.
para cada componente S e para cada bicategoria b, umheap h(S, b) guarda as arestas externas de b atribuídasa S;
bicategorias: (ATIVO, ATIVO), (ATIVO, INATIVO),(INATIVO, ATIVO) e (INATIVO, INATIVO);
os heaps h(∗, b) são mantidos em um heap H(b);
arestas não atribuídas a S são mantidas em uma listaligada extra(S).
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de Klein
IdéiaAtribuir de modo adequado as arestas externas aos seusextremos.
para cada componente S e para cada bicategoria b, umheap h(S, b) guarda as arestas externas de b atribuídasa S;
bicategorias: (ATIVO, ATIVO), (ATIVO, INATIVO),(INATIVO, ATIVO) e (INATIVO, INATIVO);
os heaps h(∗, b) são mantidos em um heap H(b);
arestas não atribuídas a S são mantidas em uma listaligada extra(S).
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de Klein (continuação)
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de CHLP
Idéia
Reduzir para dois o númerode grupos em que as arestasse dividem: {ATIVO, INATIVO}e {INATIVO, INATIVO}.Dividir cada aresta em duaspartes através da adição deum novo vértice de Steinerao grafo .
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de CHLP
Idéia
Reduzir para dois o númerode grupos em que as arestasse dividem: {ATIVO, INATIVO}e {INATIVO, INATIVO}.Dividir cada aresta em duaspartes através da adição deum novo vértice de Steinerao grafo .
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de CHLP (continuação)
vantagem: é possível mover de grupo, de uma só vez, asarestas incidentes em cada componente;
preço: pequena degradação na razão de aproximação[(1 + 1
nk
) (2− 2
t
)].
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Implementação de CHLP (continuação)
vantagem: é possível mover de grupo, de uma só vez, asarestas incidentes em cada componente;
preço: pequena degradação na razão de aproximação[(1 + 1
nk
) (2− 2
t
)].
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Visão Geral
1 O Problema da Floresta de Steiner
2 Algoritmo de Goemans e WilliamsonAlguns conceitos importantesO algoritmo
3 Implementações do Algoritmo
4 Considerações Finais
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Variedade de estruturas de dados e algoritmosutilizados nas implementações
union-find;
heaps de Fibonacci;
árvores binárias balanceadas de busca;
algoritmos para a seleção do k -ésimo menor elemento emum vetor;
algoritmo para encontrar o ancestral comum mais próximode dois nós em uma árvore.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Variedade de estruturas de dados e algoritmosutilizados nas implementações
union-find;
heaps de Fibonacci;
árvores binárias balanceadas de busca;
algoritmos para a seleção do k -ésimo menor elemento emum vetor;
algoritmo para encontrar o ancestral comum mais próximode dois nós em uma árvore.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Variedade de estruturas de dados e algoritmosutilizados nas implementações
union-find;
heaps de Fibonacci;
árvores binárias balanceadas de busca;
algoritmos para a seleção do k -ésimo menor elemento emum vetor;
algoritmo para encontrar o ancestral comum mais próximode dois nós em uma árvore.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual
O Problema da Floresta de SteinerAlgoritmo de Goemans e Williamson
Implementações do AlgoritmoConsiderações Finais
Variedade de estruturas de dados e algoritmosutilizados nas implementações
union-find;
heaps de Fibonacci;
árvores binárias balanceadas de busca;
algoritmos para a seleção do k -ésimo menor elemento emum vetor;
algoritmo para encontrar o ancestral comum mais próximode dois nós em uma árvore.
Rafael Pereira Luna Implementações do Método de Aproximação Primal-Dual