2026-07-19T14:13:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15519 2024-03-06T10:55:29Z ddc:004 open_access

Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings Banchhor, Shashwat Gajjala, Rishikesh Sabharwal, Yogish Sen, Sandeep Approximation algorithms Hierarchical memory Prefix free codes In this paper, we study the problem of designing prefix-free encoding schemes having minimum average code length that can be decoded efficiently under a decode cost model that captures memory hierarchy induced cost functions. We also study a special case of this problem that is closely related to the length limited Huffman coding (LLHC) problem; we call this the soft-length limited Huffman coding problem. In this version, there is a penalty associated with each of the n characters of the alphabet whose encodings exceed a specified bound D(≤ n) where the penalty increases linearly with the length of the encoding beyond D. The goal of the problem is to find a prefix-free encoding having minimum average code length and total penalty within a pre-specified bound P. This generalizes the LLHC problem. We present an algorithm to solve this problem that runs in time O(nD). We study a further generalization in which the penalty function and the objective function can both be arbitrary monotonically non-decreasing functions of the codeword length. We provide dynamic programming based exact and PTAS algorithms for this setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shashwat Banchhor and Rishikesh Gajjala and Yogish Sabharwal and Sandeep Sen 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.8 urn:nbn:de:0030-drops-155193 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.8 eng https://creativecommons.org/licenses/by/4.0/legalcode