Algoritmos de aproximação de tempo polinomial para programação de máquinas: quantos problemas em aberto restam?

22

Em 1999, Petra Schuurman e Gerhard J. Woeginger publicaram o artigo "Algoritmos de aproximação de tempo polinomial para programação de máquinas: dez problemas em aberto" . Desde então, de acordo com o meu conhecimento, não foram exibidas análises que abordariam a mesma lista de problemas. Portanto, seria ótimo e útil se cada um de nós pudesse fazer um resumo desse tipo de alguns dos dez problemas em aberto e contribuir com isso aqui.

Dai Le
fonte
Eu não acho que isso precisava ser feito CW ...
Suresh Venkat
@Suresh Venkat: Como remover CW?
Oleksandr Bondarenko
Infelizmente, não há como transformar uma pergunta do wiki da comunidade em uma pergunta que não seja da CW. É necessário adicionar esse recurso ao mecanismo Stack Exchange em: meta.stackexchange.com/questions/6821/…
Tsuyoshi Ito
Consulte também as Perguntas frequentes sobre quando usar a tag CW: meta.cstheory.stackexchange.com/questions/225/…
Suresh Venkat

Respostas:

16

Minimização de Makespan em máquinas idênticas sob restrições de precedência

Abrir problema 1. Proporcionar um resultado inapproximability para P | p r e c | C m a x .4/3+δP|prec|Cmax

Aqui, o que vem à mente é o artigo deste ano de Ola Svensson "Programação condicionada por dureza condicional de precedência em máquinas idênticas". Em seu artigo, Ola prova que

"se o problema de uma única máquina for difícil de aproximar dentro de um fator de , o problema considerado paralelo da máquina, mesmo no caso de tempos de processamento da unidade, é difícil de aproximar dentro de um fator de 2 - ζ , onde ζ tende a 0 como ϵ tende a 0. "2ϵ2ζζϵ

Em 2008, foi publicado o artigo "Precedência restrita de programação em · óptima" que descreve um algoritmo paraP|prec,pj=1|Cmumax., Com o coeficiente de rendimento, indicado no seu título Isto melhora mediante algoritmo Coffman-Graham com ligado2-2(273p+1)P|prec,pj=1|Cmax , ondepé o número de máquinas.22pp

O artigo "Algoritmos de aproximação para agendamento de trabalhos com restrições de precedência em cadeia" por Jansen e Solis-Oba contém PTAS para e, como conseqüência, para P m | c h a i n s | C m a x como um caso especial do problema anterior.Qm|chains|CmaxPm|chains|Cmax

P|chains|CmaxP|prec|Cmax

Minimização de Makespan em máquinas uniformes sob restrições de precedência

Qm|chains|Cmax

Minimização de Makespan sob restrições de precedência com atrasos na comunicação

Minimização de Makespan em máquinas não relacionadas

Minimização de Makespan em lojas abertas

Minimização de Makespan em lojas de fluxo

22

Minimização de Makespan em lojas de trabalho

J||Cmaxmμ5/4+δJ||CmaxJ||Cmaxm de máquinas até o infinito.

J2||Cmaxμ

J||CmaxO((loglb)1ϵ)NPZTIME(2lognO(1/ϵ))J2||CmaxNPDTIME(nO(logn))

Tempo total de conclusão do trabalho sem restrições de precedência

Tempo total de conclusão do trabalho sob restrições de precedência

1|prec|Cj1|prec|wjCj2ϵ

No "Teste ótimo de código longo com um bit livre", Bansal e Khot provaram que sim, mas assumindo uma nova variante da conjectura exclusiva dos jogos.

Critérios de tempo de fluxo

1|pmtn;rj|wjFjP|pmtn;rj|Fj

O(1)1|pmtn;rj|wjFjO(1)

Ω(logPloglogP)P|pmtn;rj|FjΩ(logPloglogP)

Oleksandr Bondarenko
fonte