Output details
11 - Computer Science and Informatics
University of Oxford
Output title
The Power of Linear Programming for Valued CSPs
Type
E - Conference contribution
Name of conference/published proceedings
(FOCS ’12) Proceedings of the IEEE 53rd Annual Symposium on Foundations of Computer Science
Volume number
-
Issue number
-
First page of article
669
ISSN of proceedings
0272-5428
Year of publication
2012
Number of additional authors
0
Additional information
<12>
Answering open problems from Deineko et al (JACM'08), Kolmogorov (MFCS'11), Huber and Kolmogorov (ISCO'12), and Krokhin and Larose (SIDMA'08), we show that the minimisation problem of explicit submodular functions is tractable on arbitrary lattices and trees. In order to do so, we provide an algebraic characterisation of the classes of functions that can be minimised optimally by linear programming relaxations. This work was used in further research by Huber et al (SODA'13) and Hirai (SODA'13) and led to an invited talk at Dagstuhl in 2012 and to a Royal Society University Research Fellowship.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
2
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
