[Colloquium] TTIC Colloquium: Chandra Chekuri, University of Illinois Urbana-Champaign

[Liv Leader]

REMINDER:

When:     Wednesday, December 7 @ 11

Where:   TTIC Conference Room #530, 6045 S. Kenwood Avenue, 5th Floor

Who:      Chandra Chekuri, University of Illinois Urbana-Champaign

Title:       Algorithms for submodular objectives via continuous extensions
and dependent randomized rounding

Abstract:
A real-valued set function $f:2^N\rightarrow R$ on a finite
ground set $N$ is submodular iff $f(A) + f(B) \ge f(A \cap B) + f(A
\cup B)$ for all $A, B \subseteq N$. There has been much recent
interest in constrained submodular function optimization. This is
driven by theoretical considerations as well as applications.

In this talk we discuss a mathematical programming approach in which
one solves a relaxation of the problem by replacing the submodular
function $f$ by a continuous extension and then rounding the resulting
fractional solution. For minimization one can use the Lovasz-extension
since it is convex and for maximization we can approximately solve the
multilinear extension that was recently introduced. Dependent
randomized rounding comes up naturally when trying to round a
fractional solution to these non-linear relaxations.

The talk will describe the framework, a few representative algorithmic
results that follow, and a few insights the approach provides into
some previous results.

Host: Yury Makarychev, yury at ttic.edu



-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20111206/d36e4397/attachment.htm