Committee Selection with a Weight Constraint Based on a Pairwise Dominance Relation - Université Pierre et Marie Curie Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

Committee Selection with a Weight Constraint Based on a Pairwise Dominance Relation

Charles Delort
  • Fonction : Auteur
  • PersonId : 977652
Olivier Spanjaard
Paul Weng
  • Fonction : Auteur
  • PersonId : 952563

Résumé

This paper is devoted to a knapsack problem with a cardinality constraint when dropping the assumption of additive representability [10]. More precisely, we assume that we only have a classification of the items into ordered classes. We aim at generating the set of preferred subsets of items, according to a pairwise dominance relation between subsets that naturally extends the ordering relation over classes [4,16]. We first show that the problem reduces to a multiobjective knapsack problem with cardinality constraint. We then propose two polynomial algorithms to solve it, one based on a multiobjective dynamic programming scheme and the other on a multiobjective branch and bound procedure. We conclude by providing numerical tests to compare both approaches.
Fichier principal
Vignette du fichier
pub_1475_1_ADT11.pdf (350.31 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01285704 , version 1 (10-07-2017)

Identifiants

Citer

Charles Delort, Olivier Spanjaard, Paul Weng. Committee Selection with a Weight Constraint Based on a Pairwise Dominance Relation. 2nd International Conference on Algorithmic Decision Theory (ADT'11), Oct 2011, Piscataway, NJ, United States. pp.28-41, ⟨10.1007/978-3-642-24873-3_3⟩. ⟨hal-01285704⟩
121 Consultations
139 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More