Faster Algorithms Unlock Secrets of Stamp Collecting’s Surprisingly Hard Maths Problems

Researchers have long investigated the challenges presented by the postage stamp problem, concerning the values achievable using a limited set of stamp denominations. Léo Colisson Palais, Jean-Guillaume Dumas, and Alexis Galan, all from Univ. Grenoble Alpes and the Laboratoire Jean Kuntzmann, alongside Grenet et al., present new algorithms addressing both the local and global variations of this problem. Their work significantly advances the field by improving the time complexity and memory requirements for solving the computationally difficult local problem, while also offering a polynomial approximation algorithm for the global problem. Importantly, these algorithmic improvements facilitate more efficient homomorphic evaluation of polynomials on ciphered values, potentially benefiting secure computation applications.

Algorithms optimise solutions to NP-hard postage stamp problems and secure computation efficiently

Scientists have developed new algorithms to address the longstanding local and global postage stamp problems, achieving improvements in both computational time and memory usage. These problems centre on determining the smallest monetary value that cannot be created using a given set of stamp denominations and a limited number of stamps.
The research introduces a novel approach to the local problem, significantly reducing its complexity, and a polynomial approximation algorithm for the global problem, accompanied by a detailed complexity analysis. This work not only advances theoretical understanding of these combinatorial challenges but also offers practical benefits for secure multi-party computations.

The local postage stamp problem, defined as finding the largest value unattainable with a given set of stamps applied to an envelope with a fixed number of positions, is known to be NP-hard. Researchers have devised an algorithm that surpasses previous methods in both time complexity and memory requirements, enabling more efficient calculations for larger problem instances.

This advancement builds upon existing techniques but introduces key optimizations to streamline the search for the unattainable value. The new algorithm allows for a more exhaustive exploration of possible stamp combinations within practical computational limits. Furthermore, the study proposes a polynomial approximation algorithm for the global postage stamp problem, which focuses on identifying a set of denominations that maximizes the largest unattainable value for a fixed number of distinct denominations.

A thorough complexity analysis accompanies this algorithm, providing insights into its performance characteristics and scalability. The team evaluated several existing constructions, including those based on the Fibonacci sequence and the Alter and Barnett sequence, and demonstrated that a recursive divide and conquer algorithm, combined with a database of base cases, yields the best results.

Importantly, the algorithms developed in this study have implications beyond pure number theory. The researchers demonstrate that these algorithms can enhance secure multi-party computations on sets by enabling a more efficient homomorphic evaluation of polynomials on encrypted values. This suggests potential applications in cryptography and secure data processing, where efficient computation with encrypted data is crucial. The team has implemented these algorithms in a library called GStamps, facilitating further research and practical application of these findings.

Algorithms for calculating s-ranges and extremal bases in postage stamp problems are often computationally intensive

A central focus of this work involves algorithms designed to address the local and global postage stamp problems, both rooted in number theory and combinatorial optimisation. The research begins by considering stamps of varying denominations but identical dimensions, alongside an envelope with a fixed maximum number of stamp positions.

To tackle the local postage stamp problem, a novel algorithm was developed to determine the s-range for a given basis of size k, improving upon existing time complexity bounds and memory requirements. This algorithm efficiently calculates the largest integer that cannot be formed by summing stamps placed on the envelope, subject to a limit of ‘s’ stamps.

For the global postage stamp problem, a polynomial approximation algorithm was implemented to identify an extremal basis for specified parameters k and s. The performance of this algorithm was analysed to determine its complexity and efficiency in generating bases with s-ranges approaching those of unknown extremal bases.

A recursive divide and conquer strategy was employed, combining smaller bases to create larger ones, with a focus on balanced recursion to optimise performance. Furthermore, the study details improvements to secure multi-party computations on sets through more efficient homomorphic evaluation of polynomials on ciphered values.

The algorithms were implemented within the GStamps library, facilitating practical application and further research. The work demonstrates that, for a basis Ak = {a1, a2, · · · , ak}, the s-range, ns(Ak), is the largest integer ‘n’ such that every integer less than or equal to ‘n’ can be expressed as a sum of stamps, with no more than ‘s’ stamps used. The research also builds upon earlier constructions, such as those by Alter and Barnett, utilising the Fibonacci sequence to create effective bases, particularly when k equals s.

Asymptotic behaviour of k and s ranges in Fibonacci sequence constructions reveals predictable growth patterns

Fibonacci sequence constructions yield a k-range of nk(Fk) = f2k+1 −1, where f0 = 0, f1 = 1, and subsequent terms are defined by f(i+2) = f(i) + f(i+1). This result is supported by a full proof of the upper bound detailed in the supplementary material. Analysis of the asymptotics of ns(Ak,s) confirms these findings in both the original construction and the improved version presented in this work.

A greedy piece-wise linear algorithm, utilising a basis Gk constructed from arithmetic progressions, achieves an s-range determined by a complex equation involving q, r, and s, where k = qs + r. Solving this equation reveals a dominant term proportional to 1 + q, with an asymptotic value of α(1 + k/s)(1 + εq)s, where εq = √(1 + 4/q − 1) / 2.

When q equals 1, the common ratio simplifies to 1 + φ, the golden number. Further refinement of the Alter and Barnett construction involves balancing blocks within the basis, employing (s − r) blocks of size q and r blocks of size q + 1. This modification yields a larger asymptotic s-range for ns(Gk).

A recursive algorithm, leveraging sub-bases Ak1 and Bk2 with s-ranges ns1(Ak1) and ns2(Bk2), constructs a basis Ck of size k = k1 + k2 such that ns(Ck) ≥ (ns1(Ak1) + 1)(ns2(Bk2) + 1) − 1. Applying this recursively with k1 = k2 and s1 = s2, both powers of two, leads to a lower bound of ns(k) ≥ 1 + k/s (s − 1).

For cases where s ≥ k, a dual lower bound of ns(k) ≥ 1 + s/k (k − 1) is established, offering a performance advantage for smaller values of k compared to the Fibonacci algorithm when k approaches s. Refinement of this bound, stopping the recursion at k = 2, yields ns(k) ≥ 1 + s/k (s/k + 3) + (k^2 − 1)/4, providing an improved lower bound for the s-range.

Algorithmic advances for local and global postage stamp problem solutions continue to emerge

Researchers have developed novel algorithms to address the local and global postage stamp problems, both of which are computationally challenging. The local postage stamp problem concerns finding the smallest monetary value that cannot be created using a given set of stamp denominations within a limited number of positions on an envelope.

Conversely, the global problem seeks the set of denominations that maximizes this unattainable value for a fixed number of distinct denominations. These new algorithms represent improvements in both time complexity and memory usage for solving the local problem, and a polynomial approximation algorithm has been devised for the global problem alongside its complexity analysis.

The algorithms presented offer practical benefits by enabling more efficient homomorphic evaluation of polynomials on encrypted values. Performance evaluations demonstrate speed-ups compared to existing approaches, particularly as the number of stamps increases. Specifically, the algorithm for the local problem requires O(ksak) assignments, where k represents the number of denominations, s is the maximum number of stamps, and a is a related parameter.

The correction of the algorithm relies on iteratively refining a table of possible values, leveraging a modulo operation for efficiency and minimizing memory access. The authors acknowledge that the complexity of the algorithms is dependent on parameters such as the number of denominations and the maximum stamp value. Further research could focus on optimizing these algorithms for specific scenarios or exploring alternative approaches to reduce computational demands.