Strongly polynomial efficient approximation scheme for segmentation

Nikolaj Tatti

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)


Partitioning a sequence of length n into k coherent segments (SEG) is one of the classic optimization problems. As long as the optimization criterion is additive, SEG can be solved exactly in O(n2k) time using a classic dynamic program. Due to the quadratic term, computing the exact segmentation may be too expensive for long sequences, which has led to development of approximate solutions. We consider an existing estimation scheme that computes (1+ϵ) approximation in polylogarithmic time. We augment this algorithm, making it strongly polynomial. We do this by first solving a slightly different segmentation problem (MAXSEG), where the quality of the segmentation is the maximum penalty of an individual segment. By using this solution to initialize the estimation scheme, we are able to obtain a strongly polynomial algorithm. In addition, we consider a cumulative version of SEG, where we are asked to discover the optimal segmentation for each prefix of the input sequence. We propose a strongly polynomial algorithm that yields (1+ϵ) approximation in O(nk2/ϵ) time. Finally, we consider a cumulative version of MAXSEG, and show that we can solve the problem in O(nklog⁡k) time.

Original languageEnglish
Pages (from-to)1-8
Number of pages8
JournalInformation Processing Letters
Publication statusPublished - 1 Feb 2019
MoE publication typeA1 Journal article-refereed


  • Approximation algorithms
  • Computational complexity
  • Histogram construction
  • Segmentation
  • Strongly polynomial


Dive into the research topics of 'Strongly polynomial efficient approximation scheme for segmentation'. Together they form a unique fingerprint.

Cite this