Considering a Classical Upper Bound on the Frobenius Number

Aled Williams () and Daiki Haijima
Additional contact information
Aled Williams: Department of Mathematics, London School of Economics and Political Science, London WC2B 4RR, UK
Daiki Haijima: Department of Mathematics, London School of Economics and Political Science, London WC2B 4RR, UK

Mathematics, 2024, vol. 12, issue 24, 1-12

Abstract: In this paper, we study the (classical) Frobenius problem, namely the problem of finding the largest integer that cannot be represented as a nonnegative integer combination of given, relatively prime, (strictly) positive integers (known as the Frobenius number). The main contribution of this paper are observations regarding a previously known upper bound on the Frobenius number where, in particular, we observe that a previously presented argument features a subtle error, which alters the value of the upper bound. Despite this, we demonstrate that the subtle error does not impact upon on the validity of the upper bound, although it does impact on the upper bounds tightness. Notably, we formally state the corrected result and additionally compare the relative tightness of the corrected upper bound with the original. In particular, we show that the updated bound is tighter in all but only a relatively “small” number of cases using both formal techniques and via Monte Carlo simulation techniques.

Keywords: Frobenius problem; Frobenius number; Diophantine equations; knapsack problems; knapsack polytopes; integer programming (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/24/4029/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/24/4029/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:24:p:4029-:d:1549883

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().