#	Pagina
attuale pagina	/open-h2020/projects/206477/index.html

Opendata, web and dolomites

PowAlgDO SIGNED

Power of Algorithms in Discrete Optimisation

Total Cost €

EC-Contrib. €

Partnership

Views

Outcomes and
results

PowAlgDO 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.

solved remarkable variants convex constitute polynomial limits theoretical derive intelligence artificial science computer realm linear consistency characterising setting computational decision power satisfaction solvability progress relates optimisation secondly relaxations seek designed precise approximate classes designing applicability ultimate mathematics uniform semidefinite fundamental powerful csps lens local first everything characterisations exact time programming complexity characterise optimal efficient optimally algorithms twofold techniques extensions constraint

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 address: WELLINGTON SQUARE UNIVERSITY OFFICES city: OXFORD postcode: OX1 2JD website: www.ox.ac.uk contact info title: n.a. name: n.a. surname: n.a. function: n.a. email: n.a. telephone: n.a. fax: n.a.
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.

#	participants	country	role	EC contrib. [€]
1	THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD Organization address address: WELLINGTON SQUARE UNIVERSITY OFFICES city: OXFORD postcode: OX1 2JD website: www.ox.ac.uk contact info title: n.a. name: n.a. surname: n.a. function: n.a. email: n.a. telephone: n.a. fax: n.a.	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

List of 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.