UW Probability Seminar:
Examples of using randomization in the design of algorithms

Time

2:30 – 3:20pm, Monday, May 24, 2010

Place

CSE 305

Speaker

Claire Mathieu, Brown University

Abstract

I will show how probability and randomization can be used to design simple, yet provably efficient algorithms: using randomization for a streaming algorithm for the language of parenthesis; using randomization for an approximation algorithm for Euclidean Traveling salesman problem and for vehicle routing; and using randomization for feedback arc set in tournaments.