Algorithms for the local and the global postage stamp problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |