---
title: "Efficient Optimization of Fixed-Length Paths"
authors:
  - "Martino Ciaperoni"
  - "Nikolaos Tziavelis"
  - "Panagiotis Karras"
doi: "10.24963/ijcai.2026/245"
url: "https://ijcai.org/proceedings/2026/245"
pdf: "https://ijcai.org/proceedings/2026/0245.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "2199-2207"
track: "Main Track"
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"
---

# Efficient Optimization of Fixed-Length Paths

Martino Ciaperoni, Nikolaos Tziavelis, Panagiotis Karras

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 2199-2207. DOI: [10.24963/ijcai.2026/245](https://doi.org/10.24963/ijcai.2026/245)

## 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.