From: Paul Beame (beame@cs.washington.edu)
Date: Thu Mar 04 2004 - 12:03:51 PST
UNIVERSITY OF WASHINGTON
Seattle, Washington 98195
Department of Computer Science and Engineering
Box 352350
(206) 543-1695
COLLOQUIUM
SPEAKER: Claire Kenyon, Ecole Polytechnique, Paris
TITLE: Metric Clustering
DATE: Thursday, March 4, 2004
TIME: 3:30 pm
PLACE: EE-105
HOST: Anna Karlin
ABSTRACT:
Given n data items in a general metric space, how can we efficiently
partition them into k clusters of "similar" items? There are many models
for this ubiquitous problem, which arises in application areas such as
data mining, image recognition, medical imaging, web analysis, etc. One
measure of the quality of a k-clustering is the sum of all pairwise
distances inside the clusters, which must be minimized. We discuss
techniques and algorithms, first for the complementary problem, which can
be seen as a metric analog of Max-Cut in graphs, then for 2-clustering,
and finally sketch extensions to variants with other objective functions
or with cardinality constraints. The algorithms are based on random
sampling.
Refreshments to be served in room prior to talk.
*NOTE* This lecture will be broadcast live via the Internet. See
http://www.cs.washington.edu/news/colloq.info.html for more information.
Email: talk-info@cs.washington.edu
Info: http://www.cs.washington.edu
The University of Washington is committed to providing access, equal
opportunity and reasonable accommodation in its sevices, programs,
activities, education and employment for individuals with disabilities.
To request disability accommodation, contact the Disability Services
Office at least ten days in advance of the event at: (206) 543-6450/V,
(206) 543-6452/TTY, (206) 685-3885/FAX, or access@u.washington.edu.
------- End of Forwarded Message
_______________________________________________
Theory-talks mailing list
Theory-talks@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-talks
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Thu Mar 04 2004 - 12:04:06 PST