The Library
The Power of Linear Programming for Valued CSPs
Tools
Tools
Tools
Thapper, Johan and Živný, Stanislav (2012) The Power of Linear Programming for Valued CSPs. In: 53rd Annual Symposium on Foundations of Computer Science (FOCS'12), New Brunswick, NJ, 20-23 Oct. 2012. Published in: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS'12) pp. 669-678. ISBN 9780769548746. ISSN 0272-5428. doi:10.1109/FOCS.2012.25
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1109/FOCS.2012.25
Abstract
A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the problem is specified by a sum of cost functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs). Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation. Using this result, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) sub modular on arbitrary lattices, (2) bisubmodular (also known as k-sub modular) on arbitrary finite domains, (3) weakly (and hence strongly) tree-sub modular on arbitrary trees.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science > Computer Science | ||||
| Journal or Publication Title: | Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS'12) | ||||
| Publisher: | IEEE | ||||
| ISBN: | 9780769548746 | ||||
| ISSN: | 0272-5428 | ||||
| Book Title: | 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science | ||||
| Official Date: | October 2012 | ||||
| Dates: |
|
||||
| Page Range: | pp. 669-678 | ||||
| DOI: | 10.1109/FOCS.2012.25 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 53rd Annual Symposium on Foundations of Computer Science (FOCS'12) | ||||
| Type of Event: | Conference | ||||
| Location of Event: | New Brunswick, NJ | ||||
| Date(s) of Event: | 20-23 Oct. 2012 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
