skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Using dual approximation algorithms for scheduling problems theoretical and practical results

Hochbaum, Dorit ; Shmoys, David

Journal of the ACM, 1987-01, Vol.34 (1), p.144-162 [Periódico revisado por pares]

New York, NY: ACM

Texto completo disponível

Citações Citado por
  • Título:
    Using dual approximation algorithms for scheduling problems theoretical and practical results
  • Autor: Hochbaum, Dorit ; Shmoys, David
  • Assuntos: Algorithms ; Applied sciences ; Approximation ; Computer science; control theory; systems ; Computer systems and distributed systems. User interface ; Exact sciences and technology ; Extreme values ; Mathematical analysis ; Optimization ; Polynomials ; Run time (computers) ; Scheduling ; Software
  • É parte de: Journal of the ACM, 1987-01, Vol.34 (1), p.144-162
  • Notas: ObjectType-Article-1
    SourceType-Scholarly Journals-1
    ObjectType-Feature-2
    content type line 23
    ObjectType-Article-2
    ObjectType-Feature-1
  • Descrição: The problem of scheduling a set of n jobs on m identical machines so as to minimize the makespan time is perhaps the most well-studied problem in the theory of approximation algorithms for NP-hard optimization problems. In this paper the strongest possible type of result for this problem, a polynomial approximation scheme, is presented. More precisely, for each ε, an algorithm that runs in time O (( n /ε) 1/ε 2 ) and has relative error at most ε is given. In addition, more practical algorithms for ε = 1/5 + 2 - k and ε = 1/6 + 2 - k , which have running times O ( n ( k + log n )) and O ( n ( km 4 + log n )) are presented. The techniques of analysis used in proving these results are extremely simple, especially in comparison with the baroque weighting techniques used previously. The scheme is based on a new approach to constructing approximation algorithms, which is called dual approximation algorithms, where the aim is to find superoptimal, but infeasible, solutions, and the performance is measured by the degree of infeasibility allowed. This notion should find wide applicability in its own right and should be considered for any optimization problem where traditional approximation algorithms have been particularly elusive.
  • Editor: New York, NY: ACM
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.