Hardness and approximability of bounded access Lempel Ziv coding

DOI10.1016/J.IC.2025.105366MaRDI QIDQ6884304zbMATH OpenFDO

Authors Ferdinando Cicalese, Francesca Ugazio

Publication date 15 December 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105366

zbMATH Keywords

algorithmsAPX-hardnessLempel-Ziv compressionNP-completeness

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Cites work

• 2726. A problem on strings of beads
• A universal algorithm for sequential data compression
• An upper bound and linear-space queries on the LZ-End parsing
• Bat-LZ out of hell
• Complexity of approximating bounded variants of optimization problems
• Linear Algorithm for Data Compression via String Matching
• On the approximation ratio of LZ-end to LZ77
• On the complexity and approximability of bounded access Lempel Ziv coding
• On the number of factors in the LZ-End factorization
• Optimal LZ-end parsing is hard
• Optimization, approximation, and complexity classes
• The Lempel–Ziv Complexity of Fixed Points of Morphisms

This page was built for publication: Hardness and approximability of bounded access Lempel Ziv coding

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