| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2015-10-02 10:00 Upper and lower bounds and time complexities on the Frobenius problem obtained from analysing its additive structure Shunichi Matsubara (Aoyama Gakuin Univ.)  COMP2015-22 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | In this work, we investigate upper and lower bounds for the Frobenius problem, using some existing results in additive combinatorics. Given a relatively prime finite set A of two or more positive integers, we define the Frobenius number for A as the maximum integer g(A) that cannot be represented by any nonnegative integer combination of A. The Frobenius problem is the problem that asks for finding g(A) for a given finite set A of relatively prime two or more positive integers. The Frobenius problem is known to be solved in polynomial time if we assume the cardinality of A to be fixed. However, the problem is also known to be NP-hard under Cook-reduction if we do not set the assumption. Thus, it is important to find better upper and lower bounds for the problem. In this paper, we investigate new upper and lower bounds for the Frobenius problem by applying Mann's theorem and Plunnecke's theorem, which is known for useful tools in additive combinatorics. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | Frobenius number / upper and lower bounds for the Frobenius problem / NP-hardness / computational complexity / additive combinatorics / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 115, no. 235, COMP2015-22, pp. 1-5, Oct. 2015. | |
| Paper # | COMP2015-22 | |
| Date of Issue | 2015-09-25 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2015-22 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2015-10-02 - 2015-10-02 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2015-10-COMP |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Upper and lower bounds and time complexities on the Frobenius problem obtained from analysing its additive structure |
| Sub Title (in English) | |
| Keyword(1) | Frobenius number |
| Keyword(2) | upper and lower bounds for the Frobenius problem |
| Keyword(3) | NP-hardness |
| Keyword(4) | computational complexity |
| Keyword(5) | additive combinatorics |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Shunichi Matsubara |
| 1st Author's Affiliation | Aoyama Gakuin University (Aoyama Gakuin Univ.) |
| 2nd Author's Name | |
| 2nd Author's Affiliation | () |
| 3rd Author's Name | |
| 3rd Author's Affiliation | () |
| 4th Author's Name | |
| 4th Author's Affiliation | () |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| 7th Author's Name | |
| 7th Author's Affiliation | () |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2015-10-02 10:00:00 |
| Presentation Time | 30 minutes |
| Registration for | COMP |
| Paper # | COMP2015-22 |
| Volume (vol) | vol.115 |
| Number (no) | no.235 |
| Page | pp.1-5 |
| #Pages | 5 |
| Date of Issue | 2015-09-25 (COMP) |
[Return to Top Page]