episciences.org_9877_1675067316
1675067316
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
11
03
2022
vol. 24, no 2
Analysis of Algorithms
A heuristic technique for decomposing multisets of nonnegative integers according to the Minkowski sum
Luciano
Margara
We study the following problem. Given a multiset $M$ of nonnegative
integers, decide whether there exist and, in the positive case, compute two
nontrivial 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 NPcomplete 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 NPcomplete as
well. When multisets are considered, the problem is equivalent to the
factorization of polynomials with nonnegative 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 nonnegative 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 be used also for factoring polynomials in N[x]. We show that,
when the degree of the polynomials gets larger, our technique is much faster
than the stateoftheart algorithms implemented in commercial software like
Mathematica and MatLab.
11
03
2022
9877
https://arxiv.org/licenses/nonexclusivedistrib/1.0
arXiv:2208.00458
10.48550/arXiv.2208.00458
https://arxiv.org/abs/2208.00458v2
https://arxiv.org/abs/2208.00458v1
10.46298/dmtcs.9877
https://dmtcs.episciences.org/9877

https://dmtcs.episciences.org/10228/pdf

https://dmtcs.episciences.org/10228/pdf