[Colloquium] REMINDER: 10/1 TTIC Colloquium: Anand Louis, Indian Institute of Science

[Mary Marre via Colloquium]

*When:    *  Monday, October 1st at 11:00 am



*Where:     *TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who:        *Anand Louis, Indian Institute of Science


*Title:*        On the Complexity of Clustering Problems

*Abstract:*  Euclidean k-means clustering, a problem having numerous
applications, is NP-hard in the worst case but often solved efficiently in
practice using simple heuristics. A quest for understanding the properties
of real-world data sets that allow efficient clustering has lead to the
notion of the perturbation resilience. In the first part of the talk, I'll
describe an algorithm to recover the optimal k-means clustering in
perturbation resilient instances.
In some cases, clustering with the k-means objective may result in a few
clusters of very large cost and many clusters of small cost. This can be
undesirable when we have a budget constraint on the cost of each cluster.
Motivated by this, we study the "min-max k-means" clustering objective. In
the second part of the talk, I'll show approximation algorithms for the
min-max k-means problem.

Based on joint works with Amit Deshpande and Apoorv Vikram Singh.


*Host: *Madhur Tulsiani <madhurt at ttic.edu>

For more information on the colloquium series or to subscribe to the
mailing list,please see http://www.ttic.edu/colloquium.php


Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*


On Mon, Sep 24, 2018 at 5:50 PM Mary Marre <mmarre at ttic.edu> wrote:

> *When:    *  Monday, October 1st at 11:00 am
>
>
>
> *Where:     *TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526
>
>
>
> *Who:        *Anand Louis, Indian Institute of Science
>
>
> *Title:*        On the Complexity of Clustering Problems
>
> *Abstract:*  Euclidean k-means clustering, a problem having numerous
> applications, is NP-hard in the worst case but often solved efficiently in
> practice using simple heuristics. A quest for understanding the properties
> of real-world data sets that allow efficient clustering has lead to the
> notion of the perturbation resilience. In the first part of the talk, I'll
> describe an algorithm to recover the optimal k-means clustering in
> perturbation resilient instances.
> In some cases, clustering with the k-means objective may result in a few
> clusters of very large cost and many clusters of small cost. This can be
> undesirable when we have a budget constraint on the cost of each cluster.
> Motivated by this, we study the "min-max k-means" clustering objective. In
> the second part of the talk, I'll show approximation algorithms for the
> min-max k-means problem.
>
> Based on joint works with Amit Deshpande and Apoorv Vikram Singh.
>
>
> *Host: *Madhur Tulsiani <madhurt at ttic.edu>
>
> For more information on the colloquium series or to subscribe to the
> mailing list,please see http://www.ttic.edu/colloquium.php
>
>
>
> Mary C. Marre
> Administrative Assistant
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 517*
> *Chicago, IL  60637*
> *p:(773) 834-1757*
> *f: (773) 357-6970*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20181001/3863b8aa/attachment-0001.html>