Pour savoir comment effectuer et gérer un dépôt de document, consultez le « Guide abrégé – Dépôt de documents » sur le site Web de la Bibliothèque. Pour toute question, écrivez à corpus@ulaval.ca.
 

Personne :
Picard-Cantin, Émilie

En cours de chargement...
Photo de profil

Adresse électronique

Date de naissance

Projets de recherche

Structures organisationnelles

Fonction

Nom de famille

Picard-Cantin

Prénom

Émilie

Affiliation

Université Laval. Département d'informatique et de génie logiciel

ISNI

ORCID

Identifiant Canadiana

ncf11918895

person.page.name

Résultats de recherche

Voici les éléments 1 - 1 sur 1
  • PublicationAccès libre
    The balance constraint family
    (Springer, 2014-09-08) Bessière, Christian; Picard-Cantin, Émilie; Hebrard, Emmanuel; Quimper, Claude-Guy; Katsirelos, George; Kiziltan, Zeynep; Walsh, Toby
    The BALANCE constraint introduced by Beldiceanu ensures solutions are balanced. This is useful when, for example, there is a requirement for solutions to be fair. BALANCE bounds the difference B between the minimum and maximum number of occurrences of the values assigned to the variables. We show that achieving domain consistency on BALANCE is NP-hard. We therefore introduce a variant, ALLBALANCE with a similar semantics that is only polynomial to propagate. We consider various forms of ALLBALANCE and focus on ATMOSTALLBALANCE which achieves what is usually the main goal, namely constraining the upper bound on B. We provide a specialized propagation algorithm, and a powerful decomposition both of which run in low polynomial time. Experimental results demonstrate the promise of these new filtering methods.