Exact and Approximation Algorithms for Computing Smallest SESs and BMSs

Compression schemes represent repetitive strings compactly by using repeated substrings. Computing the minimum size of a representation of a given input string is important for compression and for understanding relationships between compression schemes, although this task is NP-hard for several schemes. In this paper, we introduce exact and approximation algorithms for finding smallest substring equation systems (SESs) and bidirectional macro schemes (BMSs). Specifically, for an input string of length $n$, we give deterministic and randomized algorithms for computing a smallest SES using $O^*(4^n)$ and $O^*(2^n)$ time and space, respectively. We also give a deterministic algorithm for computing a smallest BMS using $O^*(2^n)$ time and space. We further give deterministic and randomized $(1+α)$-approximation algorithms for smallest SESs using $O^*(4^{e^{-α}n})$ and $O^*(2^{e^{-α}n})$ time and space, respectively, for every $α\ge 0$. A conversion from SESs to BMSs gives $4(1+α)$-approximation algorithms for smallest BMSs with the same time and space bounds. All time bounds hold in the worst case, and the randomized algorithms return correct answers with high probability. Our algorithms adapt several approaches to exact and approximation algorithms for combinatorial problems, such as dynamic programming over determinant expansions and a greedy algorithm for monotone submodular functions.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.16164
Primary Topic
Algorithms and Data Compression
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Exact and Approximation Algorithms for Computing Smallest SESs and BMSs

Hideo Bannai, Hiroki Shibata
arXiv (Cornell University)
Algorithms and Data Compression
preprint

Exact and Approximation Algorithms for Computing Smallest SESs and BMSs

Hideo Bannai, Hiroki Shibata
preprint en

Abstract

Compression schemes represent repetitive strings compactly by using repeated substrings. Computing the minimum size of a representation of a given input string is important for compression and for understanding relationships between compression schemes, although this task is NP-hard for several schemes. In this paper, we introduce exact and approximation algorithms for finding smallest substring equation systems (SESs) and bidirectional macro schemes (BMSs). Specifically, for an input string of length $n$, we give deterministic and randomized algorithms for computing a smallest SES using $O^*(4^n)$ and $O^*(2^n)$ time and space, respectively. We also give a deterministic algorithm for computing a smallest BMS using $O^*(2^n)$ time and space. We further give deterministic and randomized $(1+α)$-approximation algorithms for smallest SESs using $O^*(4^{e^{-α}n})$ and $O^*(2^{e^{-α}n})$ time and space, respectively, for every $α\ge 0$. A conversion from SESs to BMSs gives $4(1+α)$-approximation algorithms for smallest BMSs with the same time and space bounds. All time bounds hold in the worst case, and the randomized algorithms return correct answers with high probability. Our algorithms adapt several approaches to exact and approximation algorithms for combinatorial problems, such as dynamic programming over determinant expansions and a greedy algorithm for monotone submodular functions.

arXiv (Cornell University)
Algorithms and Data Compression
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon