UM ALGORITMO PARA DETERMINAR UM LIMITE SUPERIOR PARA O PROBLEMA DA CONTAGEM DE INTERVALO

Vol 53, 2021 - 139586
Trabalho completo (oral)
Favorite this paper
How to cite this paper?
Abstract

O emprego de técnicas de otimização combinatória no problema da contagem de intervalo foi explorado por Joos et al., resolvendo de forma eficiente uma versão restrita do problema da contagem de intervalo 2. Para o problema de determinar a contagem de intervalo geral, nenhuma técnica semelhante é conhecida atualmente. Elaboramos formulações de programação quadrática, levando a um algoritmo pseudopolinomial, para fornecer um limite superior na contagem de intervalo geral de ordens, que é empiricamente mostrado como próximo aos respectivos valores reais. Para a classe de semiordens, o limite superior é mostrado ser justo.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
  • 2 Universidade Federal do Rio de Janeiro
Track
  • 19 - TAG - Theory and Algorithms in Graphs
Keywords
Contagem de Intervalo
Limite superior algorítmico
Programação quadrática