{"created":"2021-03-01T06:22:39.587642+00:00","id":19568,"links":{},"metadata":{"_buckets":{"deposit":"46ce534e-3425-4209-9ef6-c77ef06ef0ac"},"_deposit":{"id":"19568","owners":[],"pid":{"revision_id":0,"type":"depid","value":"19568"},"status":"published"},"_oai":{"id":"oai:soar-ir.repo.nii.ac.jp:00019568","sets":["1221:1222"]},"author_link":["105072","105073"],"item_1628147817048":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_ab4af688f83e57aa","subitem_version_type":"AM"}]},"item_6_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2014","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicPageEnd":"604","bibliographicPageStart":"582","bibliographicVolumeNumber":"69","bibliographic_titles":[{"bibliographic_title":"ALGORITHMICA"}]}]},"item_6_description_20":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"We address generalized versions of the Huffman and Alphabetic Tree Problem where the cost caused by each individual leaf i, instead of being linear, depends on its depth in the tree by an arbitrary function. The objective is to minimize either the total cost or the maximum cost among all leaves. We review and extend the known results in this direction and devise a number of new algorithms and hardness proofs. It turns out that the Dynamic Programming approach for the Alphabetic Tree Problem can be extended to arbitrary cost functions, resulting in a time O(n (4)) optimal algorithm using space O(n (3)). We identify classes of cost functions where the well-known trick to reduce the runtime by a factor of n via a \"monotonicity\" property can be applied. For the generalized Huffman Tree Problem we show that even the k-ary version can be solved by a generalized version of the Coin Collector Algorithm of Larmore and Hirschberg (in Proc. SODA'90, pp. 310-318, 1990) when the cost functions are nondecreasing and convex. Furthermore, we give an O(n (2)logn) algorithm for the worst case minimization variants of both the Huffman and Alphabetic Tree Problem with nondecreasing cost functions. Investigating the limits of computational tractability, we show that the Huffman Tree Problem in its full generality is inapproximable unless P = NP, no matter if the objective function is the sum of leaf costs or their maximum. The alphabetic version becomes NP-hard when the leaf costs are interdependent.","subitem_description_type":"Abstract"}]},"item_6_description_30":{"attribute_name":"資源タイプ（コンテンツの種類）","attribute_value_mlt":[{"subitem_description":"Article","subitem_description_type":"Other"}]},"item_6_description_5":{"attribute_name":"引用","attribute_value_mlt":[{"subitem_description":"ALGORITHMICA. 69(3): 582-604 (2014)","subitem_description_type":"Other"}]},"item_6_link_3":{"attribute_name":"信州大学研究者総覧へのリンク","attribute_value_mlt":[{"subitem_link_text":"Fujiwara, Hiroshi","subitem_link_url":"http://soar-rd.shinshu-u.ac.jp/profile/ja.OmSVOFnU.html"}]},"item_6_link_67":{"attribute_name":"WoS","attribute_value_mlt":[{"subitem_link_url":"http://gateway.isiknowledge.com/gateway/Gateway.cgi?&GWVersion=2&SrcAuth=ShinshuUniv&SrcApp=ShinshuUniv&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000335752000005"}]},"item_6_publisher_4":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"SPRINGER"}]},"item_6_relation_48":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"10.1007/s00453-013-9755-6"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1007/s00453-013-9755-6","subitem_relation_type_select":"DOI"}}]},"item_6_rights_62":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"The original publication is available at www.springerlink.com"}]},"item_6_source_id_35":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0178-4617","subitem_source_identifier_type":"ISSN"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Fujiwara, Hiroshi"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Jacobs, Tobias"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2018-03-09"}],"displaytype":"detail","filename":"On_the_Huffman_and_Alphabetic_Tree_Problem_with_General_Cost_Functions.pdf","filesize":[{"value":"150.9 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"On_the_Huffman_and_Alphabetic_Tree_Problem_with_General_Cost_Functions.pdf","url":"https://soar-ir.repo.nii.ac.jp/record/19568/files/On_the_Huffman_and_Alphabetic_Tree_Problem_with_General_Cost_Functions.pdf"},"version_id":"ba948fb8-057d-40a5-a846-f256997d430b"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"Optimal tree","subitem_subject_scheme":"Other"},{"subitem_subject":"Binary tree","subitem_subject_scheme":"Other"},{"subitem_subject":"Multi-ary tree","subitem_subject_scheme":"Other"},{"subitem_subject":"Dynamic programming","subitem_subject_scheme":"Other"},{"subitem_subject":"Huffman coding","subitem_subject_scheme":"Other"},{"subitem_subject":"Alphabetic tree","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"On the Huffman and Alphabetic Tree Problem with General Cost Functions","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"On the Huffman and Alphabetic Tree Problem with General Cost Functions","subitem_title_language":"en"}]},"item_type_id":"6","owner":"1","path":["1222"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2018-03-09"},"publish_date":"2018-03-09","publish_status":"0","recid":"19568","relation_version_is_last":true,"title":["On the Huffman and Alphabetic Tree Problem with General Cost Functions"],"weko_creator_id":"1","weko_shared_id":-1},"updated":"2022-12-14T04:15:41.074497+00:00"}