EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4151. The McNugget-Knapsack Connection: Refining Upper Bounds on the Frobenius Number with Operational Research Applications

Invited abstract in session TC-52: Exact methods in combinatorial optimization (Contributed), stream Combinatorial Optimization.

Tuesday, 12:30-14:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Aled Williams
Mathematics, London School of Economics and Political Science
2. Daiki Haijima
London School of Economics and Political Science

Abstract

We study the classical Frobenius problem, which seeks to find the largest integer that cannot be represented as a nonnegative integral combination of given relatively prime positive integers, termed the Frobenius number. The Frobenius problem is known by other names within the literature such as the money-changing problem, the coin problem, the chicken McNugget problem and the Diophantine problem of Frobenius.

The Frobenius number is an important quantity in operational research where, from a geometric viewpoint, it is the maximal right-hand side such that the corresponding knapsack problem is integer infeasible. Further, given that the knapsack problem is NP-hard, there is a rich history on this problem. Note that computing the Frobenius number in general is NP-hard and, as such, there has been a much research into producing upper bounds on the Frobenius number.

The main contributions are observations regarding a previously known upper bound. In particular, we observe that a previously presented argument features a subtle error that alters the value of the bound. Despite this, we show that the error does not impact upon on the bound’s validity, although it does impact on its tightness. We 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 and simulation-based techniques. This is joint work with Daiki Haijima.

Keywords

Status: accepted

Back to the list of papers