![]() |
COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. | ![]() |
University of Cambridge > Talks.cam > Cambridge Algorithms talks > The complexity of finite-valued CSPs
The complexity of finite-valued CSPsAdd to your list(s) Download to your calendar using vCal
If you have a question about this talk, please contact Dr Thomas Sauerwald. Let L be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. We are interested in the problem of minimising a function given explicitly as a sum of functions from L. We establish a dichotomy theorem with respect to exact solvability for all finite-valued languages defined on domains of arbitrary finite size. We present a simple algebraic condition that characterises the tractable cases. Moreover, we show that a single algorithm based on linear programming solves all tractable cases. Furthermore, we show that there is a single reason for intractability; namely, a very specific reduction from Max-Cut. (based on work published at FOCS ’12 and STOC ’13, joint work with J.Thapper) This talk is part of the Cambridge Algorithms talks series. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsBrain and Consciousness CTSRD - CRASH-worthy Trusted Systems R&D Sir Andrew Motion Visits Cambridge in War Poets Event Peptide Mini-Symposium Computer Laboratory Computer Architecture Group Meeting One Day Meeting - 5th Annual Symposium of the Cambridge Computational Biology InstituteOther talksMeasuring Designing: Design Cognitiometrics, Physiometrics & Neurometrics Ethics for the working mathematician, seminar 11: Winning with mathematics The Object of My Affection: stories of love from the Fitzwilliam collection Adaptation in log-concave density estimation Exploring the Galaxy's alpha-element abundances and globular cluster populations with hydrodynamic simulations Panel comparisons: Challenor, Ginsbourger, Nobile, Teckentrup and Beck |