| 講演名 | 2016-09-06 フロベニウスの問題の近似困難性と被覆半径問題の関係について 松原 俊一(青学大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 与えられた $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 |
| 資料番号 | COMP2016-16 |
| 発行日 | 2016-08-30 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2016/9/6(から1日開催) |
| 開催地（和） | 富山県立大学 |
| 開催地（英） | Toyama Prefectural University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 伊藤 大雄(電通大) |
| 委員長氏名（英） | Hiroo Itoh(Univ. of Electro-Comm.) |
| 副委員長氏名（和） | 宇野 裕之(阪府大) |
| 副委員長氏名（英） | Yuushi Uno(Osaka Pref. Univ.) |
| 幹事氏名（和） | 脊戸 和寿(成蹊大) / 斎藤 寿樹(神戸大) |
| 幹事氏名（英） | Kazuhisa Seto(Seikei Univ.) / Toshiki Saito(Kobe Univ.) |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | フロベニウスの問題の近似困難性と被覆半径問題の関係について |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| 第 1 著者 氏名（和/英） | 松原 俊一 / Shunichi Matsubara |
| 第 1 著者 所属（和/英） | 青山学院大学(略称：青学大) Aoyama Gakuin University(略称：Aoyama Gakuin Univ.) |
| 発表年月日 | 2016-09-06 |
| 資料番号 | COMP2016-16 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | COMP-211 |
| ページ範囲 | pp.15-16(COMP), |
| ページ数 | 2 |
| 発行日 | 2016-08-30 (COMP) |