Published in

Elsevier, Theoretical Computer Science, 2-3(403), p. 192-201, 2008

DOI: 10.1016/j.tcs.2008.03.029

Links

Tools

Export citation

Search in Google Scholar

Soft constraint abstraction based on semiring homomorphism

Journal article published in 2007 by Sanjiang Li ORCID, Mingsheng Ying
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

The semiring-based constraint satisfaction problems (semiring CSPs), proposed by Bistarelli, Montanari and Rossi [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraints solving and optimization, Journal of the ACM 44 (2) (1997) 201–236], is a very general framework of soft constraints. In this paper we propose an abstraction scheme for soft constraints that uses semiring homomorphism. To find optimal solutions of the concrete problem, we first work in the abstract problem and find its optimal solutions, and then use them to solve the concrete problem.In particular, we show that a mapping preserves optimal solutions if and only if it is an order-reflecting semiring homomorphism. Moreover, for a semiring homomorphism α and a problem P over S, if t is optimal in α(P), then there is an optimal solution of P such that has the same value as t in α(P).