skip to main content
Idioma:

Finding Worst-Case Instances of, and Lower Bounds for, Online Algorithms Using Genetic Algorithms

Kosoresow, Andrew P. ; Johnson, Matthew P.

AI 2002: Advances in Artificial Intelligence, 2002, p.344-355 [Periódico revisado por pares]

Berlin, Heidelberg: Springer Berlin Heidelberg

Texto completo disponível

Citações Citado por
  • Título:
    Finding Worst-Case Instances of, and Lower Bounds for, Online Algorithms Using Genetic Algorithms
  • Autor: Kosoresow, Andrew P. ; Johnson, Matthew P.
  • Assuntos: Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Computer science; control theory; systems ; Evolutionary algorithms ; Exact sciences and technology ; genetic algorithms ; online algorithms ; optimization algorithms ; search ; Theoretical computing
  • É parte de: AI 2002: Advances in Artificial Intelligence, 2002, p.344-355
  • Descrição: This paper presents a novel application of Genetic Algorithms, as an empirical method in the analysis of algorithms. Online Algorithms are designed for the case in which the problem input does not arrive in its totality, as in Offline Algorithms, but arrives piece by piece, during the course of the computation. Generating worst-case instances for these algorithms, both for use as test cases and as lower-bound proofs, is often non-trivial. We study the use of Genetic Algorithms as a novel method for finding worst-case instances of online problems, including versions of the Taxicab Problem. These worst-case instances give us lower bounds on the non-competitiveness of the approximation algorithms used. In particular, our experimental results demonstrate that 6.93 is a lower bound on the competitive ratio of the hedging and optimal offline algorithms on the Hard Planar Taxicab Problem. This experimental result has theoretical implications for the study of the problem, i.e., further research to prove an upper bound of 7 may be warranted.
  • Editor: Berlin, Heidelberg: Springer Berlin Heidelberg
  • 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.