# Finding optimal set for a sum of a product function over a 2D lattice

Given a 2D lattice with coordinates $1 \leq x \leq c$ and $1 \leq y \leq d$, we define $f(x, y) = xy$.

We wish to find a boolean function $I(x,y)$ that determines in $O(1)$ time whether or not $(x,y)$ belongs to the set of points $S$ of size $k$ such that the sum $Z(S) = \sum_{(x,y) \in S} f(x,y)$ is smaller or equal to any other set of size $k$. One may use $O(c+d+k)$ time and space to construct $I$.

Is this possible? Is this a known problem (my search turned up nothing)? Can https://en.wikipedia.org/wiki/Divisor_summatory_function and its approximation help us?

Motivation: I work in NLP and am trying to find an optimal way of storing part of a word-word cooccurrence matrix in memory and part on disk. This matrix is very sparse. I'm making the simplifying assumption that the probability of two works co-occurring is proportional to their unigram frequencies. By ranking words in terms of frequency, we get the $c$ and $d$ terms. So the smaller the ranks $c$ and $d$, the more likely they are to co-occur, so this value should be stored in memory. Since there will be billions of lookups, $I$ needs to be fast.

Thanks!

• Corrected bounds. Will add more details that motivate the question. Not a textbook. Something that came up in my research. Trying to find optimal caching strategy for an NLP problem. Dec 22 '16 at 4:35
• Motivation added! Dec 23 '16 at 16:20

The set $S$ must have the following form: there must exist a threshold $t$ such that:

• If $xy < t$, then $(x,y)$ is in $S$.
• Some or all of the points $(x,y)$ with $xy=t$ are in $S$.
• If $xy > t$, then $(x,y)$ is not in $S$.

Moreover, in the second bullet, it doesn't matter which points with $xy=t$ you put into $S$; all that matters is how many of them you put into $S$. Finally, notice that the locus of points $(x,y)$ such that $xy=t$ forms a hyperbola.

It follows that one way to parametrize the set is as

$$S = \{(x,y) : xy < t \text{ or } (xy=t \text{ and } x<u)\},$$

for some parameters $t,u$. It's clear that, given $t,u$, membership can tested in $O(1)$ time, i.e., your oracle will run in $O(1)$ time, as required.

So, we simply need to select suitable values of $t,u$ during the precomputation to construct $I$. How can we do that?

One easy way is to use binary search. Notice that it's easy to count the number of lattice points $(x,y)$ such that $xy < t$ in $O(c)$ time: just iterate over $x=1,2,\dots,c$ and count the number of values $y$ such that $xy < t$, i.e., such that $y < t/x$; there are $\lfloor (t-1)/x \rfloor$ of them, so we sum that over $x=1,2,\dots,c$. Now use binary search on $t$ until you find the largest $t$ such that the number of such points is at most $k$. This gives you the value of $t$. It also gives you the number of points $(x,y)$ such that $xy<t$; call that number $k_0$.

Once you know the value of $t$, the next step is to choose a suitable value for $u$. We'll need to choose $u$ so that there are exactly $k-k_0$ lattice points $(x,y)$ such that $xy=t$ and $x<u$. Finding $u$ can be done by iterating over $x=1,2,\dots,c$; for each $x$, check whether $y=t/x$ is an integer, keep track of how many lattice points you've found, and stop once you've found $k-k_0$ of them.

In the end, the precomputation requires something like $O(\min(c,d) \log k)$ time and the oracle can be computed in $O(1)$ time. The precomputation can probably be done even faster through implementation tricks and/or some number theory, but given your problem statement, I'm guessing this might already be good enough.

• A lot to chew on here D.W. Give me a day or two to think it over. Looks good though. Thank you for your contribution. Had you seen something similar before? Dec 22 '16 at 20:47
• I'm trying to understand how your algorithm's set $S$ of size $k$ necessarily has $Z(S) \leq Z(S')$ for any $S'$ of size $k$ that is not equal to $S$. Think you can sketch a proof? Perhaps by contradiction: Suppose there is an $S'$ such that $Z(S') < Z(S)$. Then $t'$ must less than $t$, which is impossible because... Dec 23 '16 at 16:32
• @Alexandre, it's a very simple argument: if you have a bunch of numbers and want to form a set of size $k$ whose sum is minimal, you have to take the $k$ smallest numbers. In this case, each point $(x,y)$ corresponds to a number $xy$. Taking the $k$ smallest numbers corresponds to taking a set of points of the form given at the beginning of my answer.
– D.W.
Dec 23 '16 at 18:11
• @Alexandre, alternative proof: Let $S$ be the set where $Z(S)$ is smallest. I claim $S$ has the desired form. Let $t = \max\{xy : (x,y) \in S\}$. If there was any lattice point $(x',y')$ with $x'y'<t$ that's not in $S$, you could swap it in (removing the lattice point $(x,y)$ with $xy=t$), obtaining a new set with a smaller value of $Z(\cdot)$ -- but that contradicts the assumed minimality of $S$, so that can't be possible. i.e., every lattice point $(x,y)$ with $xy<t$ is in $S$. And by defn of $t$, $S$ doesn't have any lattice point $(x,y)$ with $xy>t$. That completes the proof.
– D.W.
Dec 23 '16 at 18:14