Martin Cooper: Difference between revisions
Created page with "Title: Martin Cooper Main Research Question: Can a notion of soft arc consistency be extended to non-idempotent cost combination operators, such as Max-CSP, which allows for a more general and practical problem formulation? Methodology: The researchers proposed a small additional axiom that is satisfied by most existing soft constraints proposals. This axiom allows for the extension of soft arc consistency to non-idempotent cost combination operators. They introduced a..." |
No edit summary |
||
| Line 1: | Line 1: | ||
Title: Martin Cooper | Title: Martin Cooper | ||
Main Research Question: Can a notion of | Main Research Question: Can a notion of arc consistency be extended to constraint optimization problems with non-idempotent cost combination operators? | ||
Methodology: The | 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 | 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 | 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/ | Link to Article: https://arxiv.org/abs/0111038v2 | ||
Authors: | Authors: | ||
arXiv ID: | arXiv ID: 0111038v2 | ||
[[Category:Computer Science]] | [[Category:Computer Science]] | ||
[[Category:Arc]] | [[Category:Arc]] | ||
[[Category:Consistency]] | [[Category:Consistency]] | ||
[[Category: | [[Category:Problems]] | ||
[[Category:Cost]] | [[Category:Cost]] | ||
[[Category:Combination]] | |||
Revision as of 03:32, 24 December 2023
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