Efficient Optimization of Fixed-Length Paths

Martino Ciaperoni; Nikolaos Tziavelis; Panagiotis Karras

IJCAI 20260 citations

Efficient Optimization of Fixed-Length Paths

Martino Ciaperoni, Nikolaos Tziavelis, Panagiotis Karras

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.

Constraint Satisfaction and Optimization: Constraint optimization problemsData Mining: Big data and scalabilityData Mining: Mining graphsNatural Language Processing: SpeechSearch: Combinatorial search and optimisation

BibTeX

@inproceedings{ijcai2026_efficientoptimiz,
  title = {Efficient Optimization of Fixed-Length Paths},
  author = {Martino Ciaperoni and Nikolaos Tziavelis and Panagiotis Karras},
  booktitle = {IJCAI 2026},
  year = {2026}
}