Fast algorithm for the number of solutions in the coin problem with fixed n

Combinatorics, Mathematics of Computation 1 Minute

You need to know: Coprime integers, algorithm working in polynomial time, NP-hard problem.

Background: Given positive coprime integers a_1, a_2, \dots, a_n, denote S(a_1, a_2, \dots, a_n) the (always finite) set of positive integers which cannot be represented as \sum\limits_{i=1}^n m_i a_i for some non-negative integers m_1, m_2, \dots m_n.

The Theorem: On 8th November 2002, Alexander Barvinok and Kevin Woods submitted to arxiv a paper in which they, among other results, proved the existence of an algorithm, which, given a_1, a_2, \dots, a_n, computes the number of integers in S(a_1, a_2, \dots, a_n) in polynomial time for any fixed n.

Short context: The Frobenius coin problem, studied at least from 1882, asks to compute the largest integer in S(a_1, a_2, \dots, a_n). The problem is known to be NP-hard if n is part of the input. However, Kannan presented in 1992 a polynomial algorithm to solve it for every fixed n. The Theorem states that, for fixed n, the number of elements in S(a_1, a_2, \dots, a_n) can also be computed efficiently.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment