If you want to receive emails about the various talks going on in the department, you should subscribe to the talks list.
https://mailman.cs.washington.edu/mailman/listinfo/talks
We generally will not post reminders here, but do towards the beginning of each quarter. Also, remember that you can sign in to the blog to set preferences on the types of message you receive.
Crystal
|
Mar 28 (4 days ago)
 |
|
||
|
||||
Intriguing title on this one…!
UNIVERSITY OF WASHINGTON
Computer Science and Engineering
COLLOQUIUM
SPEAKER: Shayan Oveis Gharan, Stanford University
TITLE: New Approximation Algorithms for Traveling Salesman Problem
DATE: Thursday, April 4, 2013
TIME: 3:30pm
PLACE: EEB-105
HOST: Anup Rao
ABSTRACT:
TSP is a central and perhaps one of the most well-known problems in
theoretical computer science. Due to its combination of simplicity, appeal
to imagination, and intractability, TSP has attracted the attention of
mathematicians and computer scientists for decades. Despite this
attention, the best approximation algorithm known for TSP goes back to
1976. In his unpublished manuscript, Christofides presented a simple
3/2-approximation algorithm for the problem.
In a joint work with Saberi and Singh, we design a new approximation
algorithm for a canonical special case of the TSP known as graphic TSP.
This algorithm finally breaks the 3/2 barrier by a very small constant.
Our algorithm employs a new technique for rounding the optimum fractional
solution of linear programming relaxations of combinatorial optimization
problems, called the rounding by sampling method. Our analysis builds on
recent developments in probability theory on properties of strongly
Rayleigh measures, as well as new insights from combinatorics and
polyhedral theory. As a byproduct of our result, we show new properties of
near minimum cuts of any graph, which may be of independent interest.
Bio:
Shayan Oveis Gharan is currently finishing his PhD at Stanford University
under the supervision of Amin Saberi. Prior to Stanford, Shayan received a
BA in computer engineering from Sharif University of Technology. His
research interests include Approximation Algorithms, Spectral Algorithms,
Online Algorithms and Applied Probability. He is a recipient of several
awards including best paper award at SODA 2010 and FOCS 2011 for his works
on the Traveling Salesman Problem, Stanford Graduate Fellowship, and the
Miller Fellowship.
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/
Email: talk-info@cs.washington.edu
Info: http://www.cs.washington.edu/
(206) 543-1695
The University of Washington is committed to providing access, equal
opportunity and reasonable accomodation in its services, 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-7264 (FAX), or email at
dso@u.washington.edu.
______________________________
Cs-ugrads mailing list
Cs-ugrads@cs.washington.edu
https://mailman.cs.washington.