[Colloquium] Correction: TTI-C Talk Vladlen Koltun (2/18/05 @ 3:00pm)

[Katherine Cumming]

TOYOTA TECHNOLOGICAL INSTITUTE TALK
 
FRIDAY, February 18th 3:00 pm
TTI-C Conference Room (1427 E. 60th St. - 2nd Floor) 
Refreshments provided
 
Speaker:  Vladlen Koltun, 
Speaker's homepage: http://www.cs.berkeley.edu/~vladlen/
Title: Linear Programming and Arrangements
Abstract:
We present a new approach to designing a strongly polynomial algorithm
for linear programming. We show that linear programming on any polytope
can be reduced to linear programming on an arrangement polytope. This
opens up the possibility of designing a simplex-like strongly polynomial
algorithm without resolving the Hirsch conjecture. We show that simple
deterministic approaches cannot succeed even on arrangement polytopes,
and describe initial results towards a randomized solution. We also
present near-optimal solutions to long standing open problems in
computational geometry, including the decomposition of arrangements of
surfaces, robot motion planning with translations and rotations in three
dimensions, complexity of Voronoi diagrams in three dimensions, and
more. Bio: Vladlen Koltun is a post-doctoral researcher at University of
California, Berkeley, working with Christos Papadimitriou, Umesh
Vazirani, Richard Karp, and Ken Goldberg. His doctoral dissertation,
completed under the supervision of Micha Sharir, introduced faster
algorithms for fundamental problems in computational geometry. Dr.
Koltun is the recipient of the Rothschild postdoctoral fellowship and
the Machtey award.
If you have questions, or would like to meet the speaker, please contact
Katherine at 4-1994 or kcumming at tti-c.org. For information on future
TTI-C talks or events, please go to the TTI-C Events
<http://ttic.uchicago.edu/events/events_dyn.php>  page. 
 
 
 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20050215/d31052f5/attachment.htm