BEGIN:VCALENDAR
METHOD:PUBLISH
PRODID:-//Apple Computer\, Inc//iCal 1.0//EN
X-WR-CALNAME;VALUE=TEXT:USC
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION:Speaker: Prof. Subhash Suri, UCSB
Talk Title: Paths, Trees and Polygons
Abstract: The growing scope of combinatorial algorithms often forces us to compute structures when the data are incomplete, uncertain, or time-varying. In this talk, we revisit three classical problems (Shortest Paths, Minimum Spanning Trees, and Polygon Guarding) under such informational and sensing models, and derive new complexity bounds or impossibility results.\n
\n
In particular, we show that\n
\n
(1) if the travel times for the edges of a graph are a (polynomial) functions of time, there can be super-polynomial number of shortest paths between two nodes,\n
(2) if each of the $n$ points in the plane is present only probabilistically, computing the expected length of their minimum spanning tree is intractable, and\n
(3) many basic geometric problems such as the Art Gallery coverage of a polygon can be solved in a "binary combinatorial sensing model" that does not require knowledge of coordinates.
Biography: Subhash Suri received his Ph.D. in Computer Science from Johns Hopkins University in 1987 and B.S. in Electronics Engineering from University Of Roorkee, India in 1981. His research interests are in Algorithms, Wireless Sensor Networks, Data Streams, Computational Geometry, and Game Theory. For more information, see http://www.cs.ucsb.edu/~suri/\n
Host: Prof. Gaurav Sukhatme
SEQUENCE:5
DTSTART:20110421T153000
LOCATION:SSL 150
DTSTAMP:20110421T153000
SUMMARY:CS Colloquium
UID:EC9439B1-FF65-11D6-9973-003065F99D04
DTEND:20110421T170000
END:VEVENT
END:VCALENDAR