Strongly polynomial efficient approximation scheme for segmentation

DOI10.1016/J.IPL.2018.09.007MaRDI QIDQ1628675zbMATH OpenOpenAlexFDO

Authors Nikolaj Tatti

Publication date 5 December 2018

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.11170

zbMATH Keywords

approximation algorithmscomputational complexityhistogram constructionsegmentationstrongly polynomial

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: 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(n^{2}k)$ 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+epsilon)$ 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+epsilon)$ approximation in $O(n{k}^2/epsilon)$ time. Finally, we consider a cumulative version of MaxSeg, and show that we can solve the problem in $O(nklogk)$ time.

Recommendations

• Polynomial approximation schemes and exact algorithms for optimum curve segmentation problems
• Segmentation problems
• Fast sequence segmentation using log-linear models
• Optimal Partitioning of Sequences
• scientific article; zbMATH DE number 1775433

Cites work

• A linear-time algorithm for concave one-dimensional dynamic programming
• Data-streams and histograms
• Fast sequence segmentation using log-linear models
• Geometric applications of a matrix-searching algorithm
• Improved complexity bounds for location problems on the real line
• On the approximation of curves by line segments using dynamic programming
• Online maintenance of k-medians and k-covers on a line

Cited in

(5)

• Polynomial approximation schemes and exact algorithms for optimum curve segmentation problems
• Binary segmentation for multivariate polynomials
• The network-untangling problem: from interactions to activity timelines
• scientific article; zbMATH DE number 5371223 (Why is no real title available?)
• Column-coherent matrix decomposition

This page was built for publication: Strongly polynomial efficient approximation scheme for segmentation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1628675)