Ranking specific sets of objects

Jan Maly; Stefan Woltran

Ranking specific sets of objects

Jan Maly, Stefan Woltran

Publication: Chapter in book/Conference proceeding › Contribution to conference proceedings

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.

Original language	English
Title of host publication	Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband
Subtitle of host publication	6.-10. März 2017, Stuttgart
Editors	Bernhard Mitschang, Norbert Ritter, Holger Schwarz, Meike Klettke, Andreas Thor, Oliver Kopp, Matthias Wieland
Place of Publication	Bonn
Publisher	Gesellschaft fur Informatik (GI)
Pages	193-201
Number of pages	9
ISBN (Electronic)	9783885796602
Publication status	Published - 2017
Externally published	Yes
Event	Datenbanksysteme fur Business, Technologie und Web, BTW 2017 Workshopband - Database Systems for Business, Technology and Web, BTW 2017 Workshop - Stuttgart, Germany Duration: 6 Mar 2017 → 10 Mar 2017

Publication series

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

Conference

Conference	Datenbanksysteme fur Business, Technologie und Web, BTW 2017 Workshopband - Database Systems for Business, Technology and Web, BTW 2017 Workshop
Country/Territory	Germany
City	Stuttgart
Period	6/03/17 → 10/03/17

Bibliographical note

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

Keywords

Complexity
Ranking sets

Access to Document

https://dl.gi.de/items/0ed84d8b-e256-4a3b-aecb-68af2cce9077Licence: Unspecified

Check availability

University Library Catalogue

Cite this

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 (Eds.), Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband: 6.-10. März 2017, Stuttgart (pp. 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. editor / Bernhard Mitschang ; Norbert Ritter ; Holger Schwarz ; Meike Klettke ; Andreas Thor ; Oliver Kopp ; Matthias Wieland. Bonn : Gesellschaft fur Informatik (GI), 2017. pp. 193-201 (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI), Vol. 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 (eds), 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), vol. P-266, pp. 193-201, Datenbanksysteme fur Business, Technologie und Web, BTW 2017 Workshopband - Database Systems for Business, Technology and Web, BTW 2017 Workshop, Stuttgart, Germany, 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. ed. / Bernhard Mitschang; Norbert Ritter; Holger Schwarz; Meike Klettke; Andreas Thor; Oliver Kopp; Matthias Wieland. Bonn: Gesellschaft fur Informatik (GI), 2017. p. 193-201 (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI), Vol. P-266).

Publication: Chapter in book/Conference proceeding › Contribution to conference proceedings

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, editors, Datenbanksysteme fur Business, Technologie und Web (BTW 2017) - Workshopband: 6.-10. März 2017, Stuttgart. Bonn: Gesellschaft fur Informatik (GI). 2017. p. 193-201. (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI), Vol. P-266).

Ranking specific sets of objects

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Check availability

Other files and links

Cite this