Opendata, web and dolomites

PowAlgDO SIGNED

Power of Algorithms in Discrete Optimisation

Total Cost €

0

EC-Contrib. €

0

Partnership

0

Views

0

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

SUExp (2018)

Strategic Uncertainty: An Experimental Investigation

Read More  

DISINTEGRATION (2019)

The Mass Politics of Disintegration

Read More  

PROGRESS (2019)

The Enemy of the Good: Towards a Theory of Moral Progress

Read More