PowAlgDO SIGNED
Power of Algorithms in Discrete Optimisation
Total Cost €
0EC-Contrib. €
0Partnership
0Views
0PowAlgDO project word cloud
Explore the words cloud of the PowAlgDO project. It provides you a very rough idea of what is the project "PowAlgDO" about.
Project "PowAlgDO" data sheet
The following table provides information about the project.
| Coordinator |
THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD
Organization address contact info |
| Coordinator Country | United Kingdom [UK] |
| Project website | http://www.cs.ox.ac.uk/standa.zivny/homepage/powalgdo.html |
| Total cost | 1˙437˙367 € |
| EC max contribution | 1˙437˙367 € (100%) |
| Programme |
1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC)) |
| Code Call | ERC-2016-STG |
| Funding Scheme | ERC-STG |
| Starting year | 2017 |
| Duration (year-month-day) | from 2017-01-01 to 2021-12-31 |
Partnership
Take a look of project's partnership.
| # | ||||
|---|---|---|---|---|
| 1 | THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD | UK (OXFORD) | coordinator | 1˙437˙367.00 |
Map
Project objective
Convex relaxations, such as linear and semidefinite programming, constitute one of the most powerful techniques for designing efficient algorithms, and have been studied in theoretical computer science, operational research, and applied mathematics. We seek to establish the power convex relaxations through the lens of, and with the extensions of methods designed for, Constraint Satisfaction Problems (CSPs).
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.
Publications
| year | authors and title | journal | last update |
|---|---|---|---|
| 2019 |
Bulatov, Andrei A.; Zivny, Stanislav Approximate counting CSP seen from the other side published pages: 60:1--60:14, ISSN: , DOI: 10.4230/lipics.mfcs.2019.60 |
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) 2 | 2020-01-30 |
| 2019 |
Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Živný A Tractable Class of Binary VCSPs via M-Convex Intersection published pages: 1-41, ISSN: 1549-6325, DOI: 10.1145/3329862 |
ACM Transactions on Algorithms 15/3 | 2020-01-30 |
| 2019 |
Clément Carbonnel, David A. Cohen, Martin C. Cooper, Stanislav Živný On Singleton Arc Consistency for CSPs Defined by Monotone Patterns published pages: 1699-1727, ISSN: 0178-4617, DOI: 10.1007/s00453-018-0498-2 |
Algorithmica 81/4 | 2019-09-02 |
| 2019 |
Silvia Butti
Stanislav Zivny Sparsification of Binary CSPs published pages: , ISSN: , DOI: 10.4230/lipics.stacs.2019.17 |
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) | 2019-09-02 |
| 2019 |
Dusan Knop, Michal Pilipczuk, Marcin Wrochna Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints published pages: , ISSN: , DOI: 10.4230/lipics.stacs.2019.44 |
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) | 2019-09-02 |
| 2019 |
Gregor Matl
Stanislav Zivny Beyond Boolean Surjective VCSPs published pages: , ISSN: , DOI: 10.4230/lipics.stacs.2019.52 |
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) | 2019-09-02 |
| 2017 |
Peter Fulla, Stanislav Zivny The Complexity of Boolean Surjective General-Valued CSPs published pages: , ISSN: , DOI: 10.4230/LIPIcs.MFCS.2017.4 |
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) | 2019-06-13 |
| 2018 |
Carbonnel, Clement; Cohen, David A.; Cooper, Martin C.; Zivny, Stanislav On Singleton Arc Consistency for CSPs Defined by Monotone Patterns published pages: , ISSN: , DOI: 10.4230/LIPIcs.STACS.2018.19 |
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) | 2019-06-13 |
| 2017 |
Peter Fulla, Stanislav Živný On planar valued CSPs published pages: 104-118, ISSN: 0022-0000, DOI: 10.1016/j.jcss.2017.03.005 |
Journal of Computer and System Sciences 87 | 2019-06-13 |
| 2018 |
Yuni Iwamasa, Kazuo Murota, Stanislav Živný Discrete convexity in joint winner property published pages: 78-88, ISSN: 1572-5286, DOI: 10.1016/j.disopt.2018.01.001 |
Discrete Optimization 28 | 2019-06-13 |
| 2017 |
David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Andrei Krokhin, Robert Powell, Stanislav Živný Binarisation for Valued Constraint Satisfaction Problems published pages: 2279-2300, ISSN: 0895-4801, DOI: 10.1137/16M1088107 |
SIAM Journal on Discrete Mathematics 31/4 | 2019-06-13 |
| 2018 |
Hirai, Hiroshi ; Iwamasa, Yuni ; Murota, Kazuo ; Zivny, Stanislav Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection published pages: , ISSN: , DOI: 10.4230/LIPIcs.STACS.2018.39 |
2019-06-13 | |
| 2018 |
Johan Thapper, Stanislav Živný The Limits of SDP Relaxations for General-Valued CSPs published pages: 1-22, ISSN: 1942-3454, DOI: 10.1145/3201777 |
ACM Transactions on Computation Theory 10/3 | 2019-06-13 |
| 2017 |
Martin C. Cooper and Stanislav Zivny The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns published pages: , ISSN: 1860-5974, DOI: 10.23638/LMCS-13(4:26)2017 |
Logical Methods in Computer Science | 2019-06-13 |
| 2017 |
Johan Thapper, Stanislav Živný The Power of Sherali--Adams Relaxations for General-Valued CSPs published pages: 1241-1279, ISSN: 0097-5397, DOI: 10.1137/16M1079245 |
SIAM Journal on Computing 46/4 | 2019-06-13 |
| 2017 |
Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Živný Functional clones and expressibility of partition functions published pages: 11-39, ISSN: 0304-3975, DOI: 10.1016/j.tcs.2017.05.001 |
Theoretical Computer Science 687 | 2019-06-13 |
| 2018 |
Jacob Focke, Leslie Ann Goldberg, Stanislav Živný The Complexity of Counting Surjective Homomorphisms and Compactions published pages: 1772-1781, ISSN: , DOI: 10.1137/1.9781611975031.116 |
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-13 |
Are you the coordinator (or a participant) of this project? Plaese send me more information about the "POWALGDO" project.
For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.
Send me an email (fabio@fabiodisconzi.com) and I put them in your project's page as son as possible.
Thanks. And then put a link of this page into your project's website.
The information about "POWALGDO" are provided by the European Opendata Portal: CORDIS opendata.
More projects from the same programme (H2020-EU.1.1.)
PROTECHT (2020)
Providing RObust high TECHnology Tags based on linear carbon nanostructures
Read MoreNEUROPRECISE (2019)
Precision medicine in traumatic brain injury using individual neurosteroid response
Read MoreEllipticPDE (2019)
Regularity and singularities in elliptic PDE's: beyond monotonicity formulas
Read More