{"updated":"2025-01-22T15:36:17.251359+00:00","links":{},"id":33623,"created":"2025-01-18T23:02:24.993535+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00033623","sets":["1164:2735:2790:2795"]},"path":["2795"],"owner":"1","recid":"33623","title":["いくつかのハイパーグラフ問題に対する　Primal - Dual近似アルゴリズムについて"],"pubdate":{"attribute_name":"公開日","attribute_value":"1999-02-18"},"_buckets":{"deposit":"f2a928ba-8eb9-4d66-b787-fca1c9aac316"},"_deposit":{"id":"33623","pid":{"type":"depid","value":"33623","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"いくつかのハイパーグラフ問題に対する　Primal - Dual近似アルゴリズムについて","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"いくつかのハイパーグラフ問題に対する　Primal - Dual近似アルゴリズムについて"},{"subitem_title":"On Primal - Dual Approximation Algorithms for Several Hypergraph Problems","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"1999-02-18","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"広島大学大学院工学研究科情報工学専攻"},{"subitem_text_value":"広島大学工学部第二類回路・システム工学講座"},{"subitem_text_value":"広島大学工学部第二類回路・システム工学講座"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Engineering, Hiroshima University","subitem_text_language":"en"},{"subitem_text_value":"Department of Circuits and Systems, Faculty of Engineering, Hiroshima University","subitem_text_language":"en"},{"subitem_text_value":"Department of Circuits and Systems, Faculty of Engineering, Hiroshima University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/33623/files/IPSJ-MPS98023003.pdf"},"date":[{"dateType":"Available","dateValue":"2001-02-18"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-MPS98023003.pdf","filesize":[{"value":"676.3 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"17"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"7633d211-1857-45fb-83a5-2a4548ae3113","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 1999 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"竹下, 和彦"},{"creatorName":"藤戸, 敏弘"},{"creatorName":"渡邉, 敏正"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kazuhiko, Takeshita","creatorNameLang":"en"},{"creatorName":"Toshihiro, Fujito","creatorNameLang":"en"},{"creatorName":"Toshimasa, Watanabe","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN10505667","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"ハイパーグラフは，頂点集合とその部分集合（ハイパー辺）族から構成される．ハイパーグラフ問題はグラフ問題の一般化であるが，ハイパーグラフ問題に対する近似解法に関する研究はグラフ問題ほど進んでいない．本稿では，The generalized Steiner tree problemをはじめとするいくつかのグラフ問題をハイパーグラフ上に一般化し，これらの問題の近似解法について考える．具体的には，Goemans，Williamson[2］がグラフ問題に対して提案した主双対法に基づく近似アルゴリズムをハイパーグラフ問題に適用できるように拡張し，その近似解のコストが最悪の場合でも最適解のコストのk倍以下であることを示す．ここで，kは入力ハイパーグラフ中のハイパー辺次数の最大値である．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"A hypergraph consists of a vertex set and a family of its subsets. Although hypergraph problems are a generalization of graph problems, it seems that research results on approximation algorithms for hypergraph problems are much less than those for graph problems. In this paper, we propose approximation algorithms for several hypergraph problems including the generalized Steiner tree problem for hypergraphs : the primal-dual approximation algorithm provided by Goemans and Williamson[2] is adapted for solving these hypergraph problems. The main result is that the proposed algorithm outputs an approximation solution of cost at most k times the optimal, where k is the maximum size of hyperedges in a given hypergraph.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"24","bibliographic_titles":[{"bibliographic_title":"情報処理学会研究報告数理モデル化と問題解決（MPS）"}],"bibliographicPageStart":"19","bibliographicIssueDates":{"bibliographicIssueDate":"1999-02-18","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"15(1998-MPS-023)","bibliographicVolumeNumber":"1999"}]},"relation_version_is_last":true,"weko_creator_id":"1"}}