Hola,
¿eres nuevo aquí?

Regístrate gratis y conecta tu empresa con financiación pública, partners y proyectos.

Tengo cuenta

Regístrate

Ver video

PEAC

Financiado

Cerrado

Provably Correct Efficient Algorithms for Clustering

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 wh... ver más

28/02/2019

UCPH

200K€

Presupuesto del proyecto: 200K€

Líder del proyecto

KOBENHAVNS UNIVERSITET No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

Fecha límite participación Sin fecha límite de participación.

Financiación concedida El organismo H2020 notifico la concesión del proyecto el día 2019-02-28

MSCA-IF-2016: Individual Fellowships

I+D

Cerrada hace 8 años

0% 100%

Información adicional privada

No hay información privada compartida para este proyecto. Habla con el coordinador.

1 Participantes

UCPH

200.19K€ | Lider

Proyectos interesantes

RED2018-102641-T

Data Science

Software

15K€ Cerrado

MAESTRA

Data Science

Software

2M€ Cerrado

TIN2011-27479-C04-03

Data Science

Software

99K€ Cerrado

TED2021-129791B-I00

Data Science

Software

230K€ Cerrado

TIN2017-89517-P

Data Science

Software

202K€ Cerrado

PRinHDD

Data Science

Software

234K€ Cerrado

Conecta tu I+D

¿Tienes un proyecto y buscas un partner? Gracias a nuestro motor inteligente podemos recomendarte los mejores socios y ponerte en contacto con ellos. Te lo explicamos en este video

Duración del proyecto: 24 meses Fecha Inicio: 2017-02-16
Fecha Fin: 2019-02-28

Líder del proyecto

KOBENHAVNS UNIVERSITET No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

Presupuesto del proyecto 200K€

Fecha límite de participación Sin fecha límite de participación.

Descripción del proyecto 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.

Conecta tu I+D

Entra hoy

¿Olvidé mi contraseña?

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores