Upload
armand-hudson
View
31
Download
0
Embed Size (px)
DESCRIPTION
Exercícios de Algoritmos Aproximativos. Exercício 1. 1/2 – \epsilon;1/2+2 \epsilon; ½ - \epsilon Sol ótima=2. Sol algoritmo =3. Exercício 1. b) Assuma que o algoritmo utiliza mais de um caminhão. Sejam T(1),...,T(m) os caminhões utilizados pelo algoritmo, do primeiro para o último. - PowerPoint PPT Presentation
Citation preview
Exercícios de Algoritmos Aproximativos
Exercício 1
a) 1/2 – \epsilon;1/2+2 \epsilon; ½ - \epsilon
Sol ótima=2. Sol algoritmo =3
Exercício 1
b) Assuma que o algoritmo utiliza mais de um caminhão. Sejam T(1),...,T(m) os caminhões utilizados pelo algoritmo, do primeiro para o último.
• Um limite inferior (w(1)+...w(n))/K• Note que não podem haver dois caminhões
consecutivos com carga menor que K/2, caso contrário toda carga deveria estar no primeiro deles.
• Seja p = m div 2. Somando a carga do caminão 2i-1 com a do caminhão 2i, para i=1,...,p concluímos que a carga total é de no mínimo K.p. Logo, pelo menos p+1 caminhões são necessários, o que garante uma aproximação de 2.
Exercício 2
a) Este problema é um caso particular do SET COVER apresentado em sala de aula. De fato, U={p(1),...,p(n)} e S={S(1),...,S(n)}, onde Si são as proteínas que distam no máximo de p(i).
Exercício 3
a) B=100 a(1)=1, a(2)=100
b) Ordene os inteiros do maior para o menor.
Execute o algoritmo proposto no item (a).
Exercício 3
Análise
Limite superior: min{B,a(1)+...+a(n)}
i) a(1)+...+a(n)<=B => algoritmo obtém ótimo
ii) a(1)+...+a(n)>B e existe inteiro maior que B/2 => O algoritmo retorna pelo menos B/2
iii) a(1)+...+a(n)>B e todo inteiro é menor que B/2.
Considere o primeiro inteiro j que não é incluído em S. Como j<=B/2, então neste ponto S já acumulou pelo menos B/2
Exercício 4
• Defina X(i)=1 se a(i) pertence a solução e x(i)=0, caso contrário
Minimize w(1)x(1) + ... + w(n)x(n)s.a.
• Seja x* a solução ótima da Programação Linear. Defina o Hitting Set H={i | x*(i)>=1/b}
jBi
ix jB ,1)(
Exercício 5
• Seja i a última máquina a terminar; j o último job processado em i e L(k) o tempo gasto pela máquina k
• Temos que L(i)-t(i) <= L(k), para todo k. Somando as desigualdades temos que
L(i) <= (L(1)+...+L(m))/ m + t(i)
• Como t(i)<=50 e (L(1)+...+L(m))/ m >=300, temos que L(i) não excede em 20% a carga média
Exercício 6
Estratégia
• Ordene os jobs em ordem decrescentes de tempos.
• Obtenha o escalonamento via List Scheduling considerando que todas as máquinas tem a mesma velocidade
Exercício 6
Análise• Sabe-se que o algoritmo acima esta a um fator de 3/2 do
ótimo quando todas as máquinas, de fato, tem a mesma velocidade.
• Seja OPT o makespan ótimo de nossa instância• Seja OPTfast o makespan ótimo para uma instância com
os mesmos jobs mas em que as máquinas lentas são substituídas por máquinas rápidas. Claramente, OPT >= OPTfast.
• A solução obtida pelo nosso algoritmo esta a um fator de 3 de OPTfast , 3/2 da aproximação x 2 devido ao fato que algumas máquinas são lentas. Portanto, esta a um fator de 3 de OPT.
Exercício 7
Algoritmo
• Considere um algoritmo que atribui a i-ésima pessoa ao anúncio com menor valor agregado no momento
Exercício 7
Análise• Defina V=v(1)+...+v(n)• Temos que V/m é um limite superior• Assuma (por contradição) que exista um anúncio i
com valor menor que V/(2m) ao término do algoritmo– Seja j um anúncio com valor maior que V/m. Este tem que
exisitir (princípio da casa dos pombos)– Pela hipótese do enunciado, j esta associado a pelo menos
duas pessoas. Note que a soma dos valores de todas as pessoas associadas a j, exceto a última, é maior que V/2m. Portanto, a última pessoa associada a j deveria ter sido associada a i, o que contradiz o funcionamento do algoritmo.
Exercício 9
Estratégia• Encontrar um subconjunto maximal M de T.Análise• Seja M* a solução ótima e seja t uma tripla
pertencente a M*. Ou t pertence a M ou t tem interseção com alguma tripla de M. Portanto, o número máximo de triplas em M*-M é 3|M|. Isso garante uma aproximação de 1/3.
Exercício 10
a) Seja v pertencente a T
Caso I) v pertence a S. Ok
Caso ii) v não pertence a S. O nó v não foi escolhido porque foi removido devido a um vizinho v’ em S com peso maior que v.
Exercício 10
b) Seja T* o conjunto independente de maior peso
A primeira desigualdade vale porque cada vértice de T*-S pode ser associado a um vértice vizinho de S-T* de peso maior. Entretanto, cada vértice de S-T* esta associado no máximo a 4 vizinhos
*** *
)(4)(4)()()(*)(TSvTSvTSv STv
SwvwvwvwvwTw