Trovare un set ottimale per una somma di una funzione del prodotto su un reticolo 2D

Question

Dato un reticolo 2D con coordinate $ 1 leq x leq c $ e $ 1 leq y leq d $, definiamo $ f (x, y) = xy $.

Desideriamo trovare una funzione booleana $ i (x, y) $ che determina in $ o (1) $ tempo indipendentemente dal fatto che $ (x, y) $ appartenga al set di punti $ s $ di dimensioni $ k $ che la somma $ z (s) = sum _ {(x, y) in s} f (x, y) $ è più piccolo o uguale a qualsiasi altra serie di dimensioni $ k $. Uno può usare $ O (c+d+k) $ tempo e spazio per costruire $ i $.

È possibile? È un problema noto (la mia ricerca non ha rivelato nulla)? Può https://en.wikipedia.org/wiki/divisor_summatory_function E la sua approssimazione ci aiuta?

Motivazione: lavoro nella PNL e sto cercando di trovare un modo ottimale per conservare una parte di una matrice di cooccurrenza di parole in memoria e parte sul disco. Questa matrice è molto scarsa. Sto sostenendo che la probabilità di due opere che si verificano in co-occorrenza è proporzionale alle loro frequenze nongram. Classificando le parole in termini di frequenza, otteniamo i termini $ c $ e $ d $. Quindi più piccoli sono i ranghi $ c $ e $ d $, più è probabile che si verifichino, quindi questo valore dovrebbe essere archiviato in memoria. Dal momento che ci saranno miliardi di ricerche, $ i $ deve essere veloce.

Grazie!