Ranking Specific Sets of Objects

Maly, Jan; Woltran, Stefan

Autor(en):

Zusammenfassung

Ranking sets of objects based on an order between the single elements has been thoroughly studied in the literature. In particular, it has been shown that it is in general impossible to find a total ranking – jointly satisfying properties as dominance and independence – on the whole power set of objects. However, in many formalisms from the area of knowledge representation one does not need to order the entire power set, since certain sets are already ruled out due to hard constraints or are not satisfying some background theory. In this paper, we address the question whether an order on a given subset of the power set of elements satisfying different variants of dominance and independence can be found. We first show that this problem is tractable when we look for partial rankings, but becomes NP-complete for total rankings.

Vollständige Referenz
BibTeX

Maly, J. & Woltran, S., (2017). Ranking Specific Sets of Objects. In: Mitschang, B., Nicklas, D., Leymann, F., Schöning, H., Herschel, M., Teubner, J., Härder, T., Kopp, O. & Wieland, M. (Hrsg.), Datenbanksysteme für Business, Technologie und Web (BTW 2017) - Workshopband. Bonn: Gesellschaft für Informatik e.V.. (S. 193-202).

@inproceedings{mci/Maly2017,
author = {Maly, Jan AND Woltran, Stefan},
title = {Ranking Specific Sets of Objects},
booktitle = {Datenbanksysteme für Business, Technologie und Web (BTW 2017) - Workshopband},
year = {2017},
editor = {Mitschang, Bernhard AND Nicklas, Daniela AND Leymann, Frank AND Schöning, Harald AND Herschel, Melanie AND Teubner, Jens AND Härder, Theo AND Kopp, Oliver AND Wieland, Matthias} ,
pages = { 193-202 },
publisher = {Gesellschaft für Informatik e.V.},
address = {Bonn}
}