Ranking specific sets of objects

Jan Maly; Stefan Woltran

Ranking specific sets of objects

Jan Maly, Stefan Woltran

Publikation: Beitrag in Buch/Konferenzband › Beitrag in Konferenzband

Abstract

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.

Originalsprache	Englisch
Titel des Sammelwerks	Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband
Untertitel des Sammelwerks	6.-10. März 2017, Stuttgart
Herausgeber*innen	Bernhard Mitschang, Norbert Ritter, Holger Schwarz, Meike Klettke, Andreas Thor, Oliver Kopp, Matthias Wieland
Erscheinungsort	Bonn
Verlag	Gesellschaft fur Informatik (GI)
Seiten	193-201
Seitenumfang	9
ISBN (elektronisch)	9783885796602
Publikationsstatus	Veröffentlicht - 2017
Extern publiziert	Ja
Veranstaltung	Datenbanksysteme fur Business, Technologie und Web, BTW 2017 Workshopband - Database Systems for Business, Technology and Web, BTW 2017 Workshop - Stuttgart, Deutschland Dauer: 6 März 2017 → 10 März 2017

Publikationsreihe

Reihe	Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)
Band	P-266
ISSN	1617-5468

Konferenz

Konferenz	Datenbanksysteme fur Business, Technologie und Web, BTW 2017 Workshopband - Database Systems for Business, Technology and Web, BTW 2017 Workshop
Land/Gebiet	Deutschland
Ort	Stuttgart
Zeitraum	6/03/17 → 10/03/17

Bibliographische Notiz

Publisher Copyright:
© 2017 Gesellschaft fur Informatik (GI). All rights reserved.

Zugriff auf Dokument

https://dl.gi.de/items/0ed84d8b-e256-4a3b-aecb-68af2cce9077Lizenz: Nicht angegeben

Verfügbarkeit prüfen

Katalog der Universitätsbibliothek

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Zitat

Maly, J., & Woltran, S. (2017). Ranking specific sets of objects. in B. Mitschang, N. Ritter, H. Schwarz, M. Klettke, A. Thor, O. Kopp, & M. Wieland (Hrsg.), Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband: 6.-10. März 2017, Stuttgart (S. 193-201). Gesellschaft fur Informatik (GI). https://dl.gi.de/items/0ed84d8b-e256-4a3b-aecb-68af2cce9077

Maly, Jan ; Woltran, Stefan. / Ranking specific sets of objects. Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband: 6.-10. März 2017, Stuttgart. Hrsg. / Bernhard Mitschang ; Norbert Ritter ; Holger Schwarz ; Meike Klettke ; Andreas Thor ; Oliver Kopp ; Matthias Wieland. Bonn : Gesellschaft fur Informatik (GI), 2017. S. 193-201 (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI), Band P-266).

@inproceedings{d05d86fe13114e1183712b9f34eeefc1,

title = "Ranking specific sets of objects",

abstract = "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.",

keywords = "Complexity, Ranking sets",

author = "Jan Maly and Stefan Woltran",

note = "Publisher Copyright: {\textcopyright} 2017 Gesellschaft fur Informatik (GI). All rights reserved.; Datenbanksysteme fur Business, Technologie und Web, BTW 2017 Workshopband - Database Systems for Business, Technology and Web, BTW 2017 Workshop ; Conference date: 06-03-2017 Through 10-03-2017",

year = "2017",

language = "English",

series = "Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)",

publisher = "Gesellschaft fur Informatik (GI)",

pages = "193--201",

editor = "Bernhard Mitschang and Norbert Ritter and Holger Schwarz and Meike Klettke and Andreas Thor and Oliver Kopp and Matthias Wieland",

booktitle = "Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband",

address = "Germany",

}

Maly, J & Woltran, S 2017, Ranking specific sets of objects. in B Mitschang, N Ritter, H Schwarz, M Klettke, A Thor, O Kopp & M Wieland (Hrsg.), Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband: 6.-10. März 2017, Stuttgart. Gesellschaft fur Informatik (GI), Bonn, Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI), Bd. P-266, S. 193-201, Datenbanksysteme fur Business, Technologie und Web, BTW 2017 Workshopband - Database Systems for Business, Technology and Web, BTW 2017 Workshop, Stuttgart, Deutschland, 6/03/17. <https://dl.gi.de/items/0ed84d8b-e256-4a3b-aecb-68af2cce9077>

Ranking specific sets of objects. / Maly, Jan; Woltran, Stefan.
Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband: 6.-10. März 2017, Stuttgart. Hrsg. / Bernhard Mitschang; Norbert Ritter; Holger Schwarz; Meike Klettke; Andreas Thor; Oliver Kopp; Matthias Wieland. Bonn: Gesellschaft fur Informatik (GI), 2017. S. 193-201 (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI), Band P-266).

Publikation: Beitrag in Buch/Konferenzband › Beitrag in Konferenzband

TY - GEN

T1 - Ranking specific sets of objects

AU - Maly, Jan

AU - Woltran, Stefan

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Complexity

KW - Ranking sets

UR - http://www.scopus.com/inward/record.url?scp=85072773559&partnerID=8YFLogxK

M3 - Contribution to conference proceedings

AN - SCOPUS:85072773559

T3 - Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)

SP - 193

EP - 201

BT - Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband

A2 - Mitschang, Bernhard

A2 - Ritter, Norbert

A2 - Schwarz, Holger

A2 - Klettke, Meike

A2 - Thor, Andreas

A2 - Kopp, Oliver

A2 - Wieland, Matthias

PB - Gesellschaft fur Informatik (GI)

CY - Bonn

T2 - Datenbanksysteme fur Business, Technologie und Web, BTW 2017 Workshopband - Database Systems for Business, Technology and Web, BTW 2017 Workshop

Y2 - 6 March 2017 through 10 March 2017

ER -

Maly J, Woltran S. Ranking specific sets of objects. in Mitschang B, Ritter N, Schwarz H, Klettke M, Thor A, Kopp O, Wieland M, Hrsg., Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband: 6.-10. März 2017, Stuttgart. Bonn: Gesellschaft fur Informatik (GI). 2017. S. 193-201. (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI), Band P-266).