2026-07-24T03:28:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7056 2024-03-06T10:39:25Z ddc:004 open_access

k-Regret Minimizing Set: Efficient Algorithms and Hardness Cao, Wei Li, Jian Wang, Haitao Wang, Kangning Wang, Ruosong Chi-Wing Wong, Raymond Zhan, Wei multi-criteria decision-making regret minimizing set top-k query We study the k-regret minimizing query (k-RMS), which is a useful operator for supporting multi-criteria decision-making. Given two integers k and r, a k-RMS returns r tuples from the database which minimize the k-regret ratio, defined as one minus the worst ratio between the k-th maximum utility score among all tuples in the database and the maximum utility score of the r tuples returned. A solution set contains only r tuples, enjoying the benefits of both top-k queries and skyline queries. Proposed in 2012, the query has been studied extensively in recent years. In this paper, we advance the theory and the practice of k-RMS in the following aspects. First, we develop efficient algorithms for k-RMS (and its decision version) when the dimensionality is 2. The running time of our algorithms outperforms those of previous ones. Second, we show that k-RMS is NP-hard even when the dimensionality is 3. This provides a complete characterization of the complexity of k-RMS, and answers an open question in previous studies. In addition, we present approximation algorithms for the problem when the dimensionality is 3 or larger. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wei Cao and Jian Li and Haitao Wang and Kangning Wang and Ruosong Wang and Raymond Chi-Wing Wong and Wei Zhan 2017 Is Part Of LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2017.11 urn:nbn:de:0030-drops-70569 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.11 eng https://creativecommons.org/licenses/by/3.0/legalcode