I'm delving into variations of the classic partition problem, specifically focusing on a version that may be termed the "Minimum Product Difference Partition Problem" (MPDPP). The traditional partition problem aims to divide a set of integers into two subsets such that the difference in their sums is minimized. In contrast, the MPDPP seeks to partition a set into two subsets where the difference between the products of the numbers in each subset is minimized.
Here's a more formal statement of the problem:
Given a finite set of positive integers $S = \{s_1, s_2, \ldots, s_n\}$, the goal is to find a partition of $S$ into two subsets $S_1$ and $S_2$ such that the absolute difference between the products of the numbers in $S_1$ and $S_2$ is minimized, i.e., minimize $| \prod_{s_i \in S_1} s_i - \prod_{s_j \in S_2} s_j |$.
This variation introduces a multiplicative aspect that seems to complicate the problem significantly. My questions are as follows:
- Has this problem or a similar one been studied in the literature? If so, could you provide references or terms used to describe it?
- What known algorithms or methods could be adapted or applied to approach solving the MPDPP?
- Are there any complexity results (e.g., NP-hardness) associated with this problem, or does it have any interesting connections to other well-known problems?
Any insights, references, or pointers to similar work would be greatly appreciated. I'm interested in both theoretical aspects and practical algorithms for approaching this problem.
The problem is NP-hard. In particular, testing whether there is a partition that leads to difference zero is known as the "Product Partition" problem, which has been proved to be (strongly) NP-complete in the following paper:
“Product Partition” and related problems of scheduling and systems reliability: Computational complexity and approximation. C.T. Ng, M.S. Barketau, T.C.E. Cheng, Mikhail Y. Kovalyov. European Journal of Operational Research, 2010, 207:601-604.
The paper also shows the existence of a FPTAS for a related problem, which I suspect might solve your problem as well.
I suspect that reviewing subsequent papers that cite it might provide a helpful starting point for checking what work has been done since then in the research literature.
Related: Subset product is (weakly) NP complete. See https://cs.stackexchange.com/q/7907/755, https://cstheory.stackexchange.com/q/16902/5038.