Efficient Algorithms for k-Regret Minimizing Sets
From MaRDI portal
Publication:4580150
DOI10.4230/LIPICS.SEA.2017.7zbMATH Open1432.68112arXiv1702.01446OpenAlexW2963960302MaRDI QIDQ4580150FDOQ4580150
Authors: Nirman Kumar, Stavros Sintos, Pankaj K. Agarwal, Subhash Suri 
Publication date: 13 August 2018
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1702.01446
Recommendations
- \(k\)-regret minimizing set: efficient algorithms and hardness
- Faster approximation algorithm for the \(k\)-regret minimizing set and related problems
- Minmax regret combinatorial optimization problems: an algorithmic perspective
- Complexity of the min-max and min-max regret assignment problems
- Approximating the min-max (regret) selecting items problem
- On the complexity of minmax regret linear programming
- Approximation of min-max and min-max regret versions of some combinatorial optimization problems
- An approximation algorithm for interval data minmax regret combinatorial optimization problems
- Improved Algorithms for the Minmax Regret 1-Median Problem
- \(k\)-regret queries using multiplicative utility functions
Cited In (10)
- Prudent \(k\)-choice functions: Properties and algorithms
- Approximating Distance Measures for the Skyline
- K-Dominance in Multidimensional Data: Theory and Applications
- Efficient processing of \(k\)-regret minimization queries with theoretical guarantees
- Diversity and freshness-aware regret minimizing set queries
- Faster approximation algorithm for the \(k\)-regret minimizing set and related problems
- \(k\)-regret queries using multiplicative utility functions
- \(k\)-regret minimizing set: efficient algorithms and hardness
- K-dominance in multidimensional data: theory and applications
- Towards strong regret minimization sets: balancing freshness and diversity in data selection
This page was built for publication: Efficient Algorithms for k-Regret Minimizing Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580150)
