Proceedings

Efficient Optimization of Fixed-Length Paths

Martino Ciaperoni, Nikolaos Tziavelis, Panagiotis Karras

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 2199-2207.

https://doi.org/10.24963/ijcai.2026/245

Keywords

  • Data Mining: Mining graphs
  • Data Mining: Big data and scalability
  • Natural Language Processing: Speech
  • Constraint Satisfaction and Optimization: Constraint optimization problems
  • Search: Combinatorial search and optimisation

Abstract

Optimization problems such as Viterbi decoding and V-optimal histogram construction seek a path of exact length L through a state space that minimizes a cost function. These problems are traditionally solved using dynamic programming (DP). A best-first-search (BFS) solution is also applicable, yet requires maintaining a priority queue. In all cases, memory usage grows linearly with both state space size and path length. In this paper, we propose CompactBFS, a framework that limits the growth of the BFS priority queue to space-efficiently determine the exact optimal cost for a fixed-length path and then constructs such a path by a divide-and-conquer strategy that eliminates the memory overhead. We apply CompactBFS to Viterbi decoding, which remains relevant to speech recognition, and V-optimal histogram construction. Our experimental results demonstrate significant gains over state-of-the-art solutions in runtime and memory consumption.

Martino Ciaperoni, Nikolaos Tziavelis, and Panagiotis Karras. 2026. Efficient Optimization of Fixed-Length Paths. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 2199–2207. https://doi.org/10.24963/ijcai.2026/245
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards