Leenen, LMeyer, TGhose, A2008-01-212008-01-212007-03Leenen, L, Meyer, T and Ghose, A. 2007. Relaxations of semiring constraint satisfaction problems. Information Processing Letters, Vol. 103(5), pp 177-1820020-0190http://hdl.handle.net/10204/1876Copyright: 2007 Elsevier Science B.VThe 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.enSemiring constraint satisfaction problemsOver-constrained problemsPreferencesSoft constraintsCombinatorial problemsArticleLeenen, L., Meyer, T., & Ghose, A. (2007). Relaxations of semiring constraint satisfaction problems. http://hdl.handle.net/10204/1876Leenen, L, T Meyer, and A Ghose "Relaxations of semiring constraint satisfaction problems." (2007) http://hdl.handle.net/10204/1876Leenen L, Meyer T, Ghose A. Relaxations of semiring constraint satisfaction problems. 2007; http://hdl.handle.net/10204/1876.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 -