We study the following problem. Given a multiset M of non-negative integers, decide whether there exist and, in the positive case, compute two non-trivial multisets whose Minkowski sum is equal to M. The Minkowski sum of two multisets A and B is a multiset containing all possible sums of any element of A and any element of B. This problem was proved to be NP-complete when multisets are replaced by sets. This version of the problem is strictly related to the factorization of boolean polynomials that turns out to be NP-complete as well. When multisets are considered, the problem is equivalent to the factorization of polynomials with non-negative integer coefficients. The computational complexity of both these problems is still unknown. The main contribution of this paper is a heuristic technique for decomposing multisets of non-negative integers. Experimental results show that our heuristic decomposes multisets of hundreds of elements within seconds, independently of the magnitude of numbers belonging to the multisets. Our heuristic can also be used for factoring polynomials in N[x]. We show that, when the degree of the polynomials gets larger, our technique is much faster than the state-of-the-art algorithms implemented in commercial software like Mathematica and MatLab.

Luciano Margara (2022). A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 24(2), 1-22 [10.46298/dmtcs.9877].

A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum

Luciano Margara
2022

Abstract

We study the following problem. Given a multiset M of non-negative integers, decide whether there exist and, in the positive case, compute two non-trivial multisets whose Minkowski sum is equal to M. The Minkowski sum of two multisets A and B is a multiset containing all possible sums of any element of A and any element of B. This problem was proved to be NP-complete when multisets are replaced by sets. This version of the problem is strictly related to the factorization of boolean polynomials that turns out to be NP-complete as well. When multisets are considered, the problem is equivalent to the factorization of polynomials with non-negative integer coefficients. The computational complexity of both these problems is still unknown. The main contribution of this paper is a heuristic technique for decomposing multisets of non-negative integers. Experimental results show that our heuristic decomposes multisets of hundreds of elements within seconds, independently of the magnitude of numbers belonging to the multisets. Our heuristic can also be used for factoring polynomials in N[x]. We show that, when the degree of the polynomials gets larger, our technique is much faster than the state-of-the-art algorithms implemented in commercial software like Mathematica and MatLab.
2022
Luciano Margara (2022). A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 24(2), 1-22 [10.46298/dmtcs.9877].
Luciano Margara
File in questo prodotto:
File Dimensione Formato  
sample-dmtcs-episciences.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Universal – Donazione al Pubblico Dominio (CC0 1.0)
Dimensione 299.32 kB
Formato Adobe PDF
299.32 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/899055
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact