チャネル割当問題の解法

• Item type: Trans(1)
• 公開日: 1999-02-15
• タイトル: チャネル割当問題の解法
• タイトル / 言語: en
• タイトル: Algorithms for channel assignment problems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: オリジナル論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: システム計画研究所
• 著者所属: 東京大学大学院
• 著者所属(英): en
• 著者所属(英): Research institute of systems planning
• 著者所属(英): en
• 著者所属(英): University of Tokyo
• 著者名: 宮本, 裕一郎; 松井, 知己
• 著者名(英): Yuichiro, Miyamoto; Tomomi, Matsui
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では 携帯電話の基地局に対するチャネル割当問題を組合せ最適化問題として定式化した. そして厳密解法 近似解決 発見的解法を提案した. またそれぞれの解法について同心円グラフを入力とする計算実験を行い 考察を行った. 厳密解法の章では 既存のパッケージソフトウェアを用いるため 整数線形計画問題へ帰着する定式化を提案した. 近似解法の章では 特定のグラフに対して5-近似の精度を保証する解法を提案した. 発見的解決の章では 2つの構築法と2つの改善法を提案し それらを組み合わせたいくつかの発見的解法を提案した.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we present algorithms for channel (frequency) assignment problems. We formulate channel assignment problems as combinatorial optimization problems. We propose an exact method, an approximation algorithm and heuristic algorithms. We also report the results of computational experiences. We formulated the problem as an integer linear programming problem and applied a package software. We present a 5-approximation algorithm for particular graphs which are similar to real instances. We propose two construction methods and two improvement methods. Our heuristic algorithms are combinations of construction methods and improvement methods.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 40, 号 SIG02(TOM1), p. 23-32, 発行日 1999-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会