{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:38:50Z","timestamp":1787341130469,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>We give a polynomial-time approximation scheme for the generalization of Huffman coding in which codeword letters have nonuniform costs (as in Morse code, where the dash is twice as long as the dot). The algorithm computes a $(1+\\epsilon)$-approximate solution in time $O(n+f(\\epsilon)\\log^3n)$, where $n$ is the input size.<\/jats:p>","DOI":"10.1137\/100794092","type":"journal-article","created":{"date-parts":[[2012,6,27]],"date-time":"2012-06-27T10:20:02Z","timestamp":1340792402000},"page":"684-713","source":"Crossref","is-referenced-by-count":9,"title":["Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme"],"prefix":"10.1137","volume":"41","author":[{"given":"Mordecai J.","family":"Golin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Neal E.","family":"Young","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,6,26]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.4310\/CIS.2001.v1.n2.a1"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/322203.322205"},{"key":"atypb3","first-page":"139","volume-title":"IRE Trans. Inform. Theory, PGIT-3","author":"Blachman N. M.","year":"1954"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2002.1213"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0063-1"},{"key":"atypb6","first-page":"211","volume-title":"Proceedings of the 6th Southeast Conference on Combinatorics, Graph Theory and Computing","author":"Cot N.","year":"1975"},{"key":"atypb7","unstructured":"N. Cot,\n                      Characterization and Design of Optimal Prefix Codes\n                      , Ph.D. thesis, Stanford University, Palo Alto, CA, 1977."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(69)90084-9"},{"key":"atypb9","first-page":"107","volume":"73","author":"Dumitrescu S.","year":"2006","journal-title":"Fund. Inform."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(69)90345-3"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/18.370161"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.926326"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/18.705558"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268388"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1080\/02331939008843538"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"atypb17","volume-title":"Codes for Mass Data Storage Systems","author":"Immink K. A. S.","year":"1999"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/0205002"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65955"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1961.1057615"},{"key":"atypb21","volume-title":"Addison--Wesley","author":"Knuth D. E.","year":"1973"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(62)90183-3"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1973.1054981"},{"key":"atypb24","unstructured":"R. S. Marcus,\n                      Discrete Noiseless Coding\n                      , M.S. thesis, Electrical Engineering Department, MIT, Cambridge, MA, 1957."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1980.1056250"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321883"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/321592.321601"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(71)90155-0"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100794092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:06:51Z","timestamp":1787339211000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100794092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/100794092"],"URL":"https:\/\/doi.org\/10.1137\/100794092","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}