Trouver un ensemble optimal pour une somme d'une fonction de produit sur un réseau 2D

Question

Étant donné un réseau 2D avec des coordonnées 1 leq x leq c $ et 1 leq y leq d $, nous définissons $ f (x, y) = xy $.

Nous souhaitons trouver une fonction booléenne $ i (x, y) $ qui détermine en $ o (1) $ de temps si $ (x, y) $ appartient à l'ensemble des points $ s $ de taille $ k $ que la somme $ z (s) = sum _ {(x, y) in s} f (x, y) $ est plus petite ou égale à tout autre ensemble de taille $ k $. On peut utiliser $ o (c + d + k) $ temps et espace pour construire $ i $.

Est-ce possible? Est-ce un problème connu (ma recherche n'a rien révélé)? Boîte https://en.wikipedia.org/wiki/divisor_sumatory_function Et son approximation nous aide?

Motivation: je travaille dans NLP et j'essaie de trouver un moyen optimal de stocker une partie d'une matrice de cooccurrence de mot de mot en mémoire et une partie sur le disque. Cette matrice est très clairsemée. Je fais l'hypothèse simplificatrice que la probabilité de deux œuvres concomitantes est proportionnelle à leurs fréquences d'unigrammes. En classant les mots en termes de fréquence, nous obtenons les termes $ c $ et $ d $. Ainsi, plus les rangs sont petits $ C $ et $ d $, plus ils sont susceptibles de coexuler, donc cette valeur doit être stockée en mémoire. Puisqu'il y aura des milliards de recherches, $ i $ doit être rapide.

Merci!