de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Multiconsistency and Robustness with Global Constraints

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44374

Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44744

Katriel,  Irit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Elbassioni, K., & Katriel, I. (2005). Multiconsistency and Robustness with Global Constraints. In Integration of AI and OR techniques in constraint programming for combinatorial optimization problems: Second International Conference, CPAIOR 2005 (pp. 168-182). Berlin, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-271C-7
Zusammenfassung
We propose a natural generalization of arc-consistency, which we call multiconsistency: A value $v$ in the domain of a variable $x$ is $k$-multiconsistent with respect to a constraint $C$ if there are at least $k$ solutions to $C$ in which $x$ is assigned the value $v$. We present algorithms that determine which edges are $k$-multiconsistent with respect to several well known global constraints. In addition, we show that finding super solutions is strictly harder than finding arbitrary solutions and suggest multiconsistency as an alternative way to search for robust solutions.