2013/02/03 by Karthik S. Gurumoorthy, Gurumoorthy, Karthik S.
Computer Science · Mathematics · #Algorithms and Data Compression #Mathematical Dynamics and Fractals #Data Management and Algorithms
paper · pdf · doi:10.48550/arxiv.1302.0487
We define a new notion of compressibility of a set of numbers through the dynamics of a polynomial function. We provide approaches to solve the problem by reducing it to the multi-criteria traveling salesman problem through a series of transformations. We then establish computational complexity results by giving some NP-completeness proofs. We also discuss about a notion of ε K-compressibility of a set, with regard to lossy compression and deduce the necessary condition for the given set to be ε K-compressible. Finally, we conclude by providing a list of open problems solutions to which could extend the applicability the our technique.