Show simple item record

Representing interval orders by weighted bases: Some complexity results

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorOzturk, Meltem*
hal.structure.identifier
dc.contributor.authorMarquis, Pierre*
dc.date.accessioned2010-12-14T13:58:21Z
dc.date.available2010-12-14T13:58:21Z
dc.date.issued2009
dc.identifier.issn0165-4896
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5300
dc.language.isoenen
dc.subjectComputational complexity
dc.subjectCompact representation of preferences
dc.subjectPreferences over combinatorial domains
dc.subject.ddc003en
dc.titleRepresenting interval orders by weighted bases: Some complexity results
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis 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.
dc.relation.isversionofjnlnameMathematical Social Sciences
dc.relation.isversionofjnlvol57
dc.relation.isversionofjnlissue3
dc.relation.isversionofjnldate2009
dc.relation.isversionofjnlpages367-388
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.mathsocsci.2008.12.011
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2019-11-12T14:47:08Z
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
representing_interval.PDF
Size:
160.3Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record