PIMS Distinguished Speakers Series - Zachary Friggstad, University of Alberta

This event is from the archives of The Notice Board. The event has already taken place and the information contained in this post may no longer be relevant or accurate.

Guest Speaker: Assistant Professor Zachary Friggstad (Univeristy of Alberta)
Day/Date: Friday, November 29 2019
Time: 12 to 12:50 p.m.
Location: C640, UHall

Abstract

The k-Means clustering model is undoubtedly the most widely used approach to clustering in practice, with applications stemming from machine learning, image processing, data mining, etc. In it, we are asked to group a collection of data points into k clusters to minimize the total squared distance between data points and the centroids of their cluster. Unfortunately, heuristic methods that are used in practice can perform poorly in some settings. Until just a few years ago, our theoretical understanding of how well one can perform this clustering task with an efficient algorithm was also limited.

I will present an overview of recent algorithms and related results in how well k-Means clustering can be addressed using polynomial-time algorithms with proven performance guarantees. Particular emphasis will be placed on my work in designing both a polynomial-time approximation scheme for k-Means clustering in constant-dimensional Euclidean space as well as a polynomial-time algorithm that finds optimal solutions for certain well-structured instances commonly referred to as "perturbation resilient" instances.

Room or Area: 
C640

Contact:

Barb Hodgson | hodgsonb@uleth.ca | (403) 329-2470 | uleth.ca/artsci/math-computer-science/pims-distinguished-speakers

Attached Files: