Limite superior algorítmico para a contagem de intervalo - Medeiros, Lívia Salgado; Oliveira, Fabiano de Souza; Szwarcfiter, Jayme Luiz (Anais do Encontro de Teoria da Computação (ETC), 2021)
O emprego de técnicas de otimização combinatória associadas ao 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 determinação da 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 ao respectivo valores reais. Para a classe de semiordens, o limite superior é mostrado como restrito.