Opendata, web and dolomites

PEAC

Provably-Correct Efficient Algorithms for Clustering

Total Cost €

0

EC-Contrib. €

0

Partnership

0

Views

0

Project "PEAC" data sheet

The following table provides information about the project.

Coordinator
KOBENHAVNS UNIVERSITET 

Organization address
address: NORREGADE 10
city: KOBENHAVN
postcode: 1165
website: www.ku.dk

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 Denmark [DK]
 Total cost 200˙194 €
 EC max contribution 200˙194 € (100%)
 Programme 1. H2020-EU.1.3.2. (Nurturing excellence by means of cross-border and cross-sector mobility)
 Code Call H2020-MSCA-IF-2016
 Funding Scheme MSCA-IF-EF-ST
 Starting year 2017
 Duration (year-month-day) from 2017-03-01   to  2019-02-28

 Partnership

Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    KOBENHAVNS UNIVERSITET DK (KOBENHAVN) coordinator 200˙194.00

Map

 Project objective

Clustering data according to similarity is ubiquitous in computer and data sciences. Similarity between data is often modeled by a distance function: two data points are close if they are similar. This induces a metric space in which each data point is associated to a point of the space. Thus, a clustering according to similarity is a partition of the points such that the distance between two points in the same part is small. Therefore, clustering problems play a crucial role in extracting information from massive datasets in various research areas. However, this problem is hard to formalise: the soundness of a particular clustering often depends on the structure of the data. This induces a gap between theory and practice: on the one hand no guarantee on the practical algorithms can be proven, on the other hand the best theoretical algorithms turn out to be noncompetitive in practice.

By focusing on both the algorithms and inputs that are relevant in practice, the PEAC project aims at rigorously analysing the cutting-edge heuristics and designing more efficient algorithms that are provably-correct for both clustering and hierarchical clustering (HC), bridging a gap between theory and practice.

Very recently, it was shown that a widely-used local search (LS) algorithm achieves the best approximation guarantees for some specific inputs. We plan to design a faster LS-based algorithm for those types of inputs to achieve both better running time and approximation guarantees than the best heuristics. We will design a non-oblivious LS algorithm to obtain a better than the current 2.675 approximation for k-median.

Dasgupta recently introduced a cost function for HC. Using this cost function, we plan to analyse the performances of widely-used heuristics for HC (e.g.: average-linkage, bisection k-means). We will characterize the real-world inputs and use the cost function to design more efficient provably-correct algorithms for HC.

 Publications

year authors and title journal last update
List of publications.
2017 Cohen-Addad, Dahlgaard, and Wulff-Nilsen.
Fast and Compact Exact Distance Oracle for Planar Graphs.
published pages: , ISSN: , DOI:
Proceedings of the Symposium on Foundations of Computer Science (FOCS) 2017. 2019-06-11
2018 Cohen-Addad, Colin de Verdière and de Mesmay.
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals.
published pages: , ISSN: , DOI:
Proceedings of the Symposium on Discrete Algorithms (SODA) 2018. 2019-06-11
2018 Cohen-Addad
A Fast Approximation Scheme for Low-Dimensional k-Means
published pages: , ISSN: , DOI:
Proceedings of the Symposium on Discrete Algorithms (SODA) 2018. 2019-06-11
2018 Cohen-Addad, de Mesmay, Rotenberg, and Roytman.
The Bane of Low-Dimensionality Clustering.
published pages: , ISSN: , DOI:
Proceedings of the Symposium on Discrete Algorithms (SODA) 2018. 2019-06-11
2018 Cohen-Addad, Kanade, Mallmann-Trenn, and Mathieu.
Hierarchical Clustering: Objective Functions and Algorithms.
published pages: , ISSN: , DOI:
Proceedings of the Symposium on Discrete Algorithms (SODA) 2018. 2019-06-11
2017 Cohen-Addad, Kanade, Mallmann-Trenn.
Hierarchical Clustering Beyond the Worst-Case.
published pages: , ISSN: , DOI:
Proceedings of the Conference on Neural Information Processing Systems (NIPS) 2017. 2019-06-11
2017 Cohen-Addad, Schwiegelshohn.
On the Local Structure of Stable Clustering Instances.
published pages: , ISSN: , DOI:
Proceedings of the Symposium on Foundations of Computer Science (FOCS) 2017. 2019-06-11

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "PEAC" 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 "PEAC" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.3.2.)

EPIC (2019)

Evolution of Planktonic Gastropod Calcification

Read More  

COLEX (2019)

Coopetition and Legislation in the Spanish Netherlands (1598-1665)

Read More  

GenEl (2020)

General readout electronics for cross-sectoral application in European research infrastructure

Read More