Find maximum number of equal subsets of size 3 using each index only once.

Question

Specifically, An array of numbers is being given(duplication allowed) and we have to find maximum numbers of subset(subset need not to be contiguous) each having size of 3 such that sum of each subset is equal. Values in array can be negative, zero or positive.
My approach so far is to run a loop for each value of sum and find out subsets of size 3 and finally report the maximum number of subset. Surely this is exponential time algorithm. I am looking for better randomized, approximate alogrithm.

Answer 1

Let $n$ be the size of the original array $S$.

Step 1. You need to calculate all possible sums of all triples - you'll get a three-dimensional array $A$ of sums. It'll take $O(n^3)$ operations. Actually, you'll need only approximately $\frac{1}{6}$ of this array, because each triple must have distinct elements from the $S$.

Step 2. You need to sort this array of sums, remembering also all the corresponding triples. It'll take $O(n^3log(n))$ operations. The sorting will allow you to partition the array $A$ into sets of triples with the same sum.

Step 3. For each set of triples with the same sum you need to solve an integer programming (IP) sub-problem, which can be approximated by a linear programming (LP) sub-problem. You have elements from the original set $S$ and triples with these elements. You need to find a largest subset of triples, satisfying the condition: each element from $S$ can participate in not more than one triple from this subset. Let's denote this condition (***).

Let $x_k \in \{0, 1\}$ be an integer variable, equal to $1$ if and only if the triple with index $k$ is included into the maximal set of triples. Then the IP criteria will be:

$$maximize(x_0 + x_1 + ... + x_{m-1})$$

where $m$ - the number of triples in the given set of triples.

In order to build constraints for the IP sub-problem you need to construct an incidence matrix $B$ between elements from $S$ and triples. The matrix $B$ will have $n$ rows and $m$ columns. Let the $b_{i,k}$ - element of the matrix $B$. The $b_{i,k} = 1$ if and only if the element from $S$ with index $i$ is a member of the triple with index $k$. The condition (***) for an element with index $i$ can be expressed in a following way:

$$b_{i,0}\cdot x_0 + b_{i,1} \cdot x_1 + ... + b_{i,m-1} \cdot x_{m-1} \le 1$$

It's well known that the IP problem is NP-hard. However, you can redefine variables $x_k$ as real-valued ones: $x_k \in [0, 1]$ and get an LP approximation for the original IP sub-problem. The LP sub-problem can be solved in polynomial time, then you'll be able to round variables $x_k$ and get integer-valued solution.

(However, I don't have any estimate for now, how good that approximation will be.)