Title: Approximation algorithms for facility location
| Speaker: | Chaitanya Swamy |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: Many optimization problems turn out to be computationally intractable, that is, we do not expect to be able to solve such problems optimally in a computationally efficient manner. One approach that has turned out to be quite successful when faced with such an intractable optimization problem, is that of designing an approximation algorithm, which is an algorithm that is guaranteed to return a near-optimal solution to the problem.
In
this
talk,
I
will
give
an
overview
of
the
field
of
approximation
algorithms
by
focusing
on
the
genre
of
facility-location
problems.
These
turn
out
to
be
useful
abstractions
of
clustering
and
supply-chain
problems,
and
arise
as
building
blocks
of
various
combinatorial-optimization
problems.