
Representing interval orders by weighted bases: Some complexity results
Ozturk, Meltem; Marquis, Pierre (2009), Representing interval orders by weighted bases: Some complexity results, Mathematical Social Sciences, 57, 3, p. 367-388. http://dx.doi.org/10.1016/j.mathsocsci.2008.12.011
Voir/Ouvrir
Type
Article accepté pour publication ou publiéDate
2009Nom de la revue
Mathematical Social SciencesVolume
57Numéro
3Éditeur
Elsevier
Pages
367-388
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Ozturk, MeltemLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Marquis, Pierre
Résumé (EN)
This paper is centered on the notion of interval order as a model for preferences. We introduce a family of representation languages for such orders, parameterized by a scale and an aggregation function. We show how interval orders can be represented by elements of those languages, called weighted bases. We identify the complexity of the main decision problems to be considered for exploiting such representations of interval orders (including the comparison problems and the non-dominance problem). We also show that our representation of interval orders based on weighted bases encompasses the penalty-based representation of complete preorders as a specific case.Mots-clés
Computational complexity; Compact representation of preferences; Preferences over combinatorial domainsPublications associées
Affichage des éléments liés par titre et auteur.
-
Le Berre, Daniel; Marquis, Pierre; Ozturk, Meltem (2009) Communication / Conférence
-
Pirlot, Marc; Tsoukiàs, Alexis; Ozturk, Meltem (2011) Article accepté pour publication ou publié
-
Ozturk, Meltem; Tsoukiàs, Alexis (2004) Communication / Conférence
-
Ozturk, Meltem; Tsoukiàs, Alexis (2006) Communication / Conférence
-
Ozturk, Meltem; Tsoukiàs, Alexis (2007) Communication / Conférence