Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.21423 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914289924702208 |
|---|---|
| author | Palais, Léo Colisson Dumas, Jean-Guillaume Galan, Alexis Grenet, Bruno Maignan, Aude |
| author_facet | Palais, Léo Colisson Dumas, Jean-Guillaume Galan, Alexis Grenet, Bruno Maignan, Aude |
| contents | We consider stamps with different values (denominations) and same dimensions, and an envelope with a fixed maximum number of stamp positions. The local postage stamp problem is to find the smallest value that cannot be realized by the sum of the stamps on the envelope. The global postage stamp problem is to find the set of denominations that maximize that smallest value for a fixed number of distinct denominations. The local problem is NP-hard and we propose here a novel algorithm that improves on both the time complexity bound and the amount of required memory. We also propose a polynomial approximation algorithm for the global problem together with its complexity analysis. Finally we show that our algorithms allow to improve secure multi-party computations on sets via a more efficient homomorphic evaluation of polynomials on ciphered values. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_21423 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Algorithms for the local and the global postage stamp problem Palais, Léo Colisson Dumas, Jean-Guillaume Galan, Alexis Grenet, Bruno Maignan, Aude Data Structures and Algorithms We consider stamps with different values (denominations) and same dimensions, and an envelope with a fixed maximum number of stamp positions. The local postage stamp problem is to find the smallest value that cannot be realized by the sum of the stamps on the envelope. The global postage stamp problem is to find the set of denominations that maximize that smallest value for a fixed number of distinct denominations. The local problem is NP-hard and we propose here a novel algorithm that improves on both the time complexity bound and the amount of required memory. We also propose a polynomial approximation algorithm for the global problem together with its complexity analysis. Finally we show that our algorithms allow to improve secure multi-party computations on sets via a more efficient homomorphic evaluation of polynomials on ciphered values. |
| title | Algorithms for the local and the global postage stamp problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.21423 |