Sum of k smallest values of affine functions
I recently found out that my problem is known as the k-th level problem, which itself is equivalent to the k-set problem in the dual plane. Since almost 50 years, it is an open problem how many sets there are exactly. At present, the best upper bound is given by $O(n k ^{1/3})$: https://en.wikipedia.org/wiki/K-set_(geometry)