Martin Cooper

Title: Martin Cooper

Main Research Question: Can a notion of arc consistency be extended to constraint optimization problems with non-idempotent cost combination operators?

Methodology: The authors proposed a weak additional axiom satisfied by most existing soft constraints proposals. They introduced a notion of soft arc consistency that extends the classical notion of arc consistency and applies to non-idempotent cost combination operators. They also presented a polynomial time algorithm for enforcing soft arc consistency.

Results: The authors demonstrated that using the additional axiom, it is possible to define a soft arc consistency that is applicable to non-idempotent cost combination operators. They showed that their algorithm has the same space and time complexities as enforcing arc consistency in CSPs for strictly monotonic cost combination operators (like Max-CSP). They also introduced a directional version of arc consistency and showed that it can potentially solve soft constraint problems on trees and imply a form of local optimality called arc irreducibility.

Implications: The extension of arc consistency to non-idempotent cost combination operators has significant implications for the field of constraint satisfaction problems. It allows for the solution of problems that were previously intractable, and it provides a more comprehensive approach to constraint optimization. The proposed algorithm and its properties offer a practical solution to these extended problems.

Link to Article: https://arxiv.org/abs/0111038v2 Authors: arXiv ID: 0111038v2