| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2016-09-06 11:30 フロベニウスの問題の近似困難性と被覆半径問題の関係について ○松原俊一（青学大）  COMP2016-16 |
|
| 抄録 | （和） | 与えられた $n$ 個の互いに素な正整数 $a_1,cdots,a_n$について，その非負整数結合 $sum_{i=1}^n c_i a_i$として表すことのできない最大数を求める問題をフロベニウス問題と言う．本論文ではフロベニウス数の近似困難性を証明する方法について，被覆半径問題を中心に調べる．この問題は，計算困難であることが示されている一方で，実験的に高速なアルゴリズムの開発もさかんである．しかし近似アルゴリズムや近似困難性についての理論的な結果はほとんど知られていない． |
| （英） | Given coprime positive integers $a_1,cdots,a_n$, we call the problem that asks the maximum integer among all positive integers that cannot be represented as nonnegative integer combinations of $a_1,cdots,a_n$ the Frobenius problem. In this paper, we investigate the inapproximability of the Frobenius problem mainly by discussing a formula between a covering radius and the Frobenius number due to Kannan. Little research has been done on the inapproximability of the Frobenius problem although the computational complexity for deterministic algorithms has been known. | |
| キーワード | （和） | フロベニウス問題 / 近似困難性 / 近似アルゴリズム / 被覆半径 / 計算複雑さ / / / |
| （英） | Frobenius problem / inapproximability / approximation algorithm / covering radius / computational complexity / / / | |
| 文献情報 | 信学技報, vol. 116, no. 211, COMP2016-16, pp. 15-16, 2016年9月. | |
| 資料番号 | COMP2016-16 | |
| 発行日 | 2016-08-30 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2016-16 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2016-09-06 - 2016-09-06 |
| 開催地（和） | 富山県立大学 |
| 開催地（英） | Toyama Prefectural University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2016-09-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | フロベニウスの問題の近似困難性と被覆半径問題の関係について |
| サブタイトル（和） | |
| タイトル（英） | On the inapproximability of the Frobenius problem and its relationship with the covering radius problem |
| サブタイトル（英） | |
| キーワード(1)（和/英） | フロベニウス問題 / Frobenius problem |
| キーワード(2)（和/英） | 近似困難性 / inapproximability |
| キーワード(3)（和/英） | 近似アルゴリズム / approximation algorithm |
| キーワード(4)（和/英） | 被覆半径 / covering radius |
| キーワード(5)（和/英） | 計算複雑さ / computational complexity |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 松原 俊一 / Shunichi Matsubara / マツバラ シュンイチ |
| 第1著者 所属（和/英） | 青山学院大学 (略称： 青学大) Aoyama Gakuin University (略称： Aoyama Gakuin Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2016-09-06 11:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2016-16 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | no.211 |
| ページ範囲 | pp.15-16 |
| ページ数 | 2 |
| 発行日 | 2016-08-30 (COMP) |
[研究会発表申込システムのトップページに戻る]