### Power of Algorithms in Discrete Optimisation (PowAlgDO)

** Principal Investigator **

** Postdoctoral Research Fellows **

- Marcin Wrochna, from 3 December 2018
- Miguel Romero, from 23 May 2017
- Clément Carbonnel, 1 March 2017 - 30 November 2018 (→ CNRS, France)

** DPhil Students **

- Jacob Focke, from 1 October 2019
- Alexandre Brandts-Longtin, from 1 October 2018
- Peter Fulla, 1 October 2017 - 30 September 2018 (→ JSPS Fellowship @ NII, Japan)

** Project Summary **

Our goal is twofold. First, to provide precise characterisations of the applicability of convex relaxations such as which problems can be solved by linear programming relaxations. Secondly, to derive computational complexity consequences such as for which classes of problems the considered algorithms are optimal in that they solve optimally everything that can be solved in polynomial time. For optimisation problems, we aim to characterise the limits of linear and semidefinite programming relaxations for exact, approximate, and robust solvability. For decision problems, we aim to characterise the limits of local consistency methods, one of the fundamental techniques in artificial intelligence, which strongly relates to linear programming relaxations.

Recent years have seen some remarkable progress on characterising the power of algorithms for a very important type of problems known as non-uniform constraint satisfaction problems and their optimisation variants. The ultimate goal of this project is to develop new techniques and establish novel results on the limits of convex relaxations and local consistency methods in a general setting going beyond the realm of non-uniform CSPs.

** Visitors **

- Caterina Viola, 14-18 October 2019
- Andrei Krokhin and Jakub Opršal, 23-27 September 2019
- Florent Capelli and Stefan Mengel, 16-20 September 2019
- Peter Fulla, 27-31 June 2019
- Martin Cooper, 1-5 April 2019
- Martin Cooper, 22-25 January 2019
- Amanda Vidal, 26-30 November 2018
- Andrei Bulatov, 9-20 July 2018
- Monaldo Mastrolilli, 15-21 April 2018
- Jakub Bulín, 29 January - 2 February 2018
- Andrei Bulatov, 10-26 July 2017
- Martin Cooper, 10-27 July 2017
- Johan Thapper, 26 June - 7 July 2017
- Yuni Iwamasa, 8-19 May 2017

** Funding information **

** Papers **

- Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, and Stanislav Živný, A tractable class of binary VCSPs via M-convex intersection,
**ACM TALG**15(3), Article No. 44, 2019. doi:10.1145/3329862 - Jacob Focke, Leslie Ann Goldberg, and Stanislav Živný, The complexity of counting surjective homomorphisms and compactions,
**SIDMA**33(2), pp. 1006-1043, 2019. doi:10.1137/17M1153182 - Clément Carbonnel, David Cohen, Martinc Cooper, and Stanislav Živný, On singleton arc consistency for CSPs defined by monotone patterns,
**Algorithmica**81(4) pp. 1699-1727, 2019. doi:10.1007/s00453-018-0498-2 - David Cohen, Martinc Cooper, Peter Jeavons, and Stanislav Živný, Binary constraint satisfaction problems defined by excluded topological minors,
**IC**264, pp. 12-31, 2019. doi:10.1016/j.ic.2018.09.013 - Peter Fulla and Hannes Uppman, and Stanislav Živný, The complexity of Boolean surjective general-valued CSPs,
**ACM ToCT**11(1), Article No. 4, 2019. doi:10.1145/3282429 - Andrei Bulatov and Stanislav Živný, Approximate counting CSP seen from the other side, Proceedings of
**MFCS'19**. - Pablo Barceló, Diego Figueira, and Miguel Romero, Boundedness of Conjunctive Regular Path Queries , Proceedings of
**ICALP'19**. doi:10.4230/LIPIcs.ICALP.2019.104 - Clément Carbonnel, Miguel Romero, and Stanislav Živný, Point-width and Max-CSPs, Proceedings of
**LICS'19**. - Eduard Eiben, Robert Ganian, Dušan Knop, Sebastian Ordyniak, Michał Pilipczuk, and Marcin Wrochna, Integer programming and incidence treedepth, Proceedings of
**IPCO'19**. doi:10.1007/978-3-030-17953-3_15 - Dušan Knop, Michał Pilipczuk, and Marcin Wrochna, Tight complexity lower bounds for integer linear programming with few constraints, Proceedings of
**STACS'19**. doi:10.4230/LIPIcs.STACS.2019.44 - Silvia Butti and Stanislav Živný, Sparsification of binary CSPs, Proceedings of
**STACS'19**. doi:10.4230/LIPIcs.STACS.2019.17 - Gregor Matl and Stanislav Živný, Beyond Boolean surjective VCSPs, Proceedings of
**STACS'19**. doi:10.4230/LIPIcs.STACS.2019.52 - Jacob Focke, Leslie Ann Goldberg, and Stanislav Živný, The complexity of approximately counting retractions, Proceedings of
**SODA'19**. doi:10.1137/1.9781611975482.133 - Johan Thapper and Stanislav Živný, The limits of SDP relaxations for general-valued CSPs,
**ACM ToCT**10(3), Article No. 12, 2018. doi:10.1145/3201777 - Yuni Iwamasa, Kazuo Murota, and Stanislav Živný, Discrete convexity in joint winner property,
**DO**28 78-88, 2018. doi:10.1016/j.disopt.2018.01.001 - Clément Carbonnel, Miguel Romero, and Stanislav Živný, The complexity of general-valued CSPs seen from the other side, Proceedings of
**FOCS'18**. doi:10.1109/FOCS.2018.00031 - Miguel Romero, The tractability frontier of well-designed SPARQL queries, Proceedings of
**PODS'18**. doi:10.1145/3196959.3196973 - Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, and Stanislav Živný, Beyond JWP: A tractable class of binary VCSPs via M-convex intersection, Proceedings of
**STACS'18**. 10.4230/LIPIcs.STACS.2018.39 - Clément Carbonnel, David Cohen, Martin Cooper, and Stanislav Živný, On singleton arc consistency for CSPs defined by monotone patterns, Proceedings of
**STACS'18**. doi:10.4230/LIPIcs.STACS.2018.19 - Jacob Focke, Leslie Ann Goldberg, and Stanislav Živný, The complexity of counting surjective homomorphisms and compactions, Proceedings of
**SODA'18**. doi:10.1137/1.9781611975031.116 - Martin Cooper and Stanislav Živný, The power of arc consistency for CSPs defined by partially-ordered forbidden patterns,
**LMCS**13(4:26) 1-32, 2017. doi:10.23638/LMCS-13(4:26)2017 - David Cohen, Martin Cooper, Peter Jeavons, Andrei Krokhin, Robert Powell, and Stanislav Živný, Binarisation for valued constraint satisfaction problems,
**SIDMA**31(4) 2279-2300, 2017. doi:10.1137/16M1088107 - Johan Thapper and Stanislav Živný, The power of Sherali-Adams relaxations for general-valued CSPs,
**SICOMP**46(4) 1241-1279, 2017. doi:10.1137/16M1079245 - Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, and Stanislav Živný, Functional clones and expressibility of partition functions,
**TCS**687 11-39, 2017. doi:10.1016/j.tcs.2017.05.001 - Peter Fulla and Stanislav Živný, On planar valued CSPs,
**JCSS**87 104-118, 2017. doi:10.1016/j.jcss.2017.03.005 - Peter Fulla and Stanislav Živný, The complexity of Boolean surjective general-valued CSPs, Proceedings of
**MFCS'17**. doi:10.4230/LIPIcs.MFCS.2017.4 - Johan Thapper and Stanislav Živný, The limits of SDP relaxations for general-valued CSPs, Proceedings of
**LICS'17**. doi:1109/LICS.2017.8005087