Unifying Arc Consistency for Semiring-Based Constraint Satisfaction and Optimization

Abstract

Bibtex entry

@Proceedings{Werner-EURO07,
  author =       {Tom{\'a}{\vs} Werner},
  title =     {Unifying Arc Consistency for Semiring-Based Constraint Satisfaction and Optimization},
  month =     {July},
  year =      {2007},
  booktitle = {22nd Conf. on Operational Research, Prague},
  note =      {Invited talk.},
  annote = {(Soft) constraint satisfaction problems are general
  problems of combinatorial optimization. They can be uni ed by
  algebraic formulation, e.g., by using two abstract operations
  forming a commutative semiring. A fundamental concept to tackle the
  crisp CSP is arc consistency. We generalize arc consistency to some
  soft CSPs and formulate it the semiring framework. We newly
  introduce sum-product arc consistency and give its relation to
  max-sum arc consistency and optimal max-sum arc consistency. We give
  a criterion that decreases after every arc consistency
  iteration.},
}