1721. The McNugget-Knapsack Connection Revisited: Evaluating the Sharpness and Structural Limitations of Frobenius Number Bounds with Operational Research Applications
Invited abstract in session WC-20: Topics in Combinatorial Optimization 2, stream Combinatorial Optimization.
Wednesday, 12:30-14:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Aled Williams
|
| Mathematics, London School of Economics and Political Science |
Abstract
We study classical bounds on the Frobenius number, which is the largest integer not expressible as a nonnegative integral combination of given relatively prime positive integers. The Frobenius problem, known in literature by names including the money-changing problem, the coin problem, the chicken McNugget problem and the Diophantine problem of Frobenius, is pivotal in operational research due to its connection with integer infeasibility in knapsack problems. From a geometric perspective, the Frobenius number represents the maximal right-hand side for which the corresponding knapsack problem remains integer infeasible. Computing the Frobenius number is NP-hard in general, motivating research into developing upper bounds.
We present a comparative analysis of existing upper bounds on the Frobenius number, evaluating their relative tightness through both theoretical and simulation-based methods. A key contribution is the proof of a fundamental limitation on upper bounds. Specifically, we show that no general upper bound with a worst-case exponent strictly less than quadratic is possible without imposing stronger conditions than coprimality.
These findings offer deeper insights into the structural constraints on Frobenius number bounds and provide guidance for future refinements.
Keywords
- Programming, Integer
- Programming, Linear
- Combinatorial Optimization
Status: accepted
Back to the list of papers