| Presentation | 2016-09-06 On the inapproximability of the Frobenius problem and its relationship with the covering radius problem Shunichi Matsubara, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Frobenius problem / inapproximability / approximation algorithm / covering radius / computational complexity |
| Paper # | COMP2016-16 |
| Date of Issue | 2016-08-30 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2016/9/6(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Toyama Prefectural University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiroo Itoh(Univ. of Electro-Comm.) |
| Vice Chair | Yuushi Uno(Osaka Pref. Univ.) |
| Secretary | Yuushi Uno(Seikei Univ.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the inapproximability of the Frobenius problem and its relationship with the covering radius problem |
| Sub Title (in English) | |
| Keyword(1) | Frobenius problem |
| Keyword(2) | inapproximability |
| Keyword(3) | approximation algorithm |
| Keyword(4) | covering radius |
| Keyword(5) | computational complexity |
| 1st Author's Name | Shunichi Matsubara |
| 1st Author's Affiliation | Aoyama Gakuin University(Aoyama Gakuin Univ.) |
| Date | 2016-09-06 |
| Paper # | COMP2016-16 |
| Volume (vol) | vol.116 |
| Number (no) | COMP-211 |
| Page | pp.pp.15-16(COMP), |
| #Pages | 2 |
| Date of Issue | 2016-08-30 (COMP) |