1
$\begingroup$

I have a collection of sets $A_i \subset \mathbb{Z}$ where I want to find the global maximum after combining the sets using sumset.

The sumset is $$ A + B = \{ a + b : a \in A , b \in B \} $$ and $R$ is the combination of each set $A_i$ $$ R = \sum A_i $$ Then with some function $f : \mathbb{Z} \rightarrow \mathbb R$, I want to select the element $x \in R$ such that $f(x)$ is maximized.

Practically, each element in a set is a 64 bit unsigned integer, so each set is bounded by $M = 2^{64}-1$ and the output of a sumset operation never produces an element exceeding that bound. Also each set is sparse.

I have a solution for this but I am looking for optimizations or different approaches. I currently use sparse polynomial convolution based on Johnson's Sparse Polynomial Arithmetic (1974) [1]. In summary, I am implementing sparse polynomial convolution first, and then iterating over terms of that result to select the element such that $f$ is maximized.

My current method is to represent each set by its characteristic function. Then the sumset operation becomes the convolution of two of polynomials. Normally, FFT would be used next but since the set is sparse, using a dense array to hold the polynomial produces many zeros, so I instead resort to using a sparse polynomial where each is a sorted array of integers representing the exponents with non-zero coefficient. This step is computed by distributing the terms of one polynomial over the other to create a set of polynomials multiplied by one term. Since each term is represented solely by the exponent, this is just adding to each value in an array, which maintains the sorted property. Then I combine them using a $k$-way merge using a heap. Then, after each convolution is performed ending with the resulting polynomial $r$, the function $f$ is mapped over the exponents of $r$, and the exponent that maximizes the value of $f$ is the solution.

I've implemented this approach and it works well on small cases, but as each $|A_i|$ increases, $|R|$ increases exponentially and won't fit in machine memory. The issue is that I am generating the entire set $R$ whereas I only need a single element of $R$. A followup would be finding the elements $x_k$ that result in the top $k$ values of $f(x_k)$, in which case generating the entire set $R$ allows it to be ranked for any value $k$.

The most recent research I found on sparse polynomial multiplication is Roche's What Can (and Can’t) we Do with Sparse Polynomials? (2018) [2], which continues from Johnson's work and notes that there hasn't been any significant change in this problem since the idea of using a heap.

[1]: http://www.cecm.sfu.ca/~mmonagan/teaching/TopicsinCA11/johnson.pdf

[2]: https://arxiv.org/pdf/1807.08289.pdf

$\endgroup$
1
$\begingroup$

Unless you have some further structure to the problem (i.e., the function) you can't do better than checking all.

$\endgroup$
1
  • $\begingroup$ Thanks, I am finding myself approaching the same conclusion. Also, the function cannot be evaluated on intermediate sets, only on the final resulting set. Unfortunately, I do not meet the requirement to give you an upvote yet. $\endgroup$ – teikou May 15 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.