10.46298/dmtcs.9877
https://dmtcs.episciences.org/9877
Margara, Luciano
Luciano
Margara
A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum
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 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 state-of-the-art algorithms implemented in commercial software like
Mathematica and MatLab.
episciences.org
Computer Science - Discrete Mathematics
arXiv.org - Non-exclusive license to distribute
2022-10-25
2022-11-03
2022-11-03
eng
journal article
arXiv:2208.00458
10.48550/arXiv.2208.00458
1365-8050
https://dmtcs.episciences.org/9877/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
vol. 24, no 2
Analysis of Algorithms
Researchers
Students