  A regret minimizing set Q is a small size representation of a much larger
database P so that user queries executed on Q return answers whose scores are
not much worse than those on the full dataset. In particular, a k-regret
minimizing set has the property that the regret ratio between the score of the
top-1 item in Q and the score of the top-k item in P is minimized, where the
score of an item is the inner product of the item's attributes with a user's
weight (preference) vector. The problem is challenging because we want to find
a single representative set Q whose regret ratio is small with respect to all
possible user weight vectors.
  We show that k-regret minimization is NP-Complete for all dimensions d >= 3.
This settles an open problem from Chester et al. [VLDB 2014], and resolves the
complexity status of the problem for all d: the problem is known to have
polynomial-time solution for d <= 2. In addition, we propose two new
approximation schemes for regret minimization, both with provable guarantees,
one based on coresets and another based on hitting sets. We also carry out
extensive experimental evaluation, and show that our schemes compute
regret-minimizing sets comparable in size to the greedy algorithm proposed in
[VLDB 14] but our schemes are significantly faster and scalable to large data
sets.
