| ID:
279167.0,
MPI für Informatik / Algorithms and Complexity Group |
| Multiconsistency and Robustness with Global Constraints |
| Authors: | Elbassioni, Khaled; Katriel, Irit |
| Editors: | Barták, Roman; Milano, Michela |
| Language: | English |
| Publisher: | Springer |
| Place of Publication: | Berlin, Germany |
| Date of Publication (YYYY-MM-DD): | 2005 |
| Title of Proceedings: | Integration of AI and OR techniques in constraint programming for combinatorial optimization problems : Second International Conference, CPAIOR 2005 |
| Start Page: | 168 |
| End Page: | 182 |
| Title of Series: | Lecture Notes in Computer Science |
| Place of Conference/Meeting: | Prague, Czech Republic |
(Start) Date of Conference/Meeting
(YYYY-MM-DD): | 2005-05-30 |
| Audience: | Experts Only |
| Intended Educational Use: | No |
| Abstract / Description: | 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. |
| Last Change of the Resource (YYYY-MM-DD): | 2005-11-17 |
| External Publication Status: | published |
| Document Type: | Conference-Paper |
| Communicated by: | Kurt Mehlhorn |
| Affiliations: | MPI für Informatik/Algorithms and Complexity Group
|
| Identifiers: | LOCALID:C1256428004B93B8-730FF40252F20B18C1256FB1004C029F-...
ISBN:3-540-26152-4 |
|
Advanced
