dc.contributor.author |
Leenen, L
|
|
dc.contributor.author |
Meyer, T
|
|
dc.contributor.author |
Ghose, A
|
|
dc.date.accessioned |
2008-01-21T13:53:55Z |
|
dc.date.available |
2008-01-21T13:53:55Z |
|
dc.date.issued |
2007-03 |
|
dc.identifier.citation |
Leenen, L, Meyer, T and Ghose, A. 2007. Relaxations of semiring constraint satisfaction problems. Information Processing Letters, Vol. 103(5), pp 177-182 |
en |
dc.identifier.issn |
0020-0190 |
|
dc.identifier.uri |
http://hdl.handle.net/10204/1876
|
|
dc.description |
Copyright: 2007 Elsevier Science B.V |
en |
dc.description.abstract |
The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. In this framework preferences can be associated with tuples of values of the variable domains. Bistarelli et al. [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraint solving and optimization, Journal of the ACM 44 (2) (1997) 201–236] defines a maximal solution to a SCSP as the best set of solution tuples for the variables in the problem. Sometimes this maximal solution may not be good enough, and in this case we want to change the constraints so that we solve a problem that is slightly different from the original problem but has an acceptable solution. We propose a relaxation of a SCSP, and use a semiring to give a measure of the difference between the original SCSP and the relaxed SCSP. We introduce a relaxation scheme but do not address the computational aspects. |
en |
dc.language.iso |
en |
en |
dc.publisher |
Elsevier Science B.V |
en |
dc.subject |
Semiring constraint satisfaction problems |
en |
dc.subject |
Over-constrained problems |
en |
dc.subject |
Preferences |
en |
dc.subject |
Soft constraints |
en |
dc.subject |
Combinatorial problems |
en |
dc.title |
Relaxations of semiring constraint satisfaction problems |
en |
dc.type |
Article |
en |
dc.identifier.apacitation |
Leenen, L., Meyer, T., & Ghose, A. (2007). Relaxations of semiring constraint satisfaction problems. http://hdl.handle.net/10204/1876 |
en_ZA |
dc.identifier.chicagocitation |
Leenen, L, T Meyer, and A Ghose "Relaxations of semiring constraint satisfaction problems." (2007) http://hdl.handle.net/10204/1876 |
en_ZA |
dc.identifier.vancouvercitation |
Leenen L, Meyer T, Ghose A. Relaxations of semiring constraint satisfaction problems. 2007; http://hdl.handle.net/10204/1876. |
en_ZA |
dc.identifier.ris |
TY - Article
AU - Leenen, L
AU - Meyer, T
AU - Ghose, A
AB - The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. In this framework preferences can be associated with tuples of values of the variable domains. Bistarelli et al. [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraint solving and optimization, Journal of the ACM 44 (2) (1997) 201–236] defines a maximal solution to a SCSP as the best set of solution tuples for the variables in the problem. Sometimes this maximal solution may not be good enough, and in this case we want to change the constraints so that we solve a problem that is slightly different from the original problem but has an acceptable solution. We propose a relaxation of a SCSP, and use a semiring to give a measure of the difference between the original SCSP and the relaxed SCSP. We introduce a relaxation scheme but do not address the computational aspects.
DA - 2007-03
DB - ResearchSpace
DP - CSIR
KW - Semiring constraint satisfaction problems
KW - Over-constrained problems
KW - Preferences
KW - Soft constraints
KW - Combinatorial problems
LK - https://researchspace.csir.co.za
PY - 2007
SM - 0020-0190
T1 - Relaxations of semiring constraint satisfaction problems
TI - Relaxations of semiring constraint satisfaction problems
UR - http://hdl.handle.net/10204/1876
ER -
|
en_ZA |