Schedule 2008
|
Presenter
|
Title and Abstract
|
Date
|
|
Fabian Chudak
D-Wave Systems
|
Title: Efficient solutions to relaxations of combinatorial problems with submodular penalties
Abstract:
Click to hide abstract
In the classical Uncapacitated Facility Location Problem, there is a
set of clients C and a set of potential facility sites F. Opening a facility
at location i \in F has a fixed cost f_i and can provide unlimited service
to clients; if client j\in C is serviced by a facility at location i \in F,
there is an associated cost of c_{ij}. The goal is to open facilities and
assign all the clients to the open facilities so as to minimize the total cost.
In this talk, we will consider a variant of the problem in which not
all clients need to be serviced. Instead, if a subset S of the clients C
is not serviced, there is a penalty cost f(S), where f is a set-function.
We make two assumptions about the penalty function f. First, we assume that the
function f is increasing, that is, the more clients that are not serviced,
the larger the penalty. And secondly, to model the economical impact of
the penalty we further assume that the function f is submodular, which can
be interpreted as a function that respects economies of scale.
This problem was introduced by Hayrapetyan, Swamy and Tardos (2005)
who also provided an approximation algorithm for the metric case that
relies on the use of the ellipsoid algorithm for solving an
exponentially large linear programming relaxation. We consider a
natural and equivalent convex relaxation of the problem based on a
novel use of the Lov\'asz extension of a submodular function and show
how it can be efficiently approximated using recent algorithms for
non-smooth convex optimization due to Nesterov (2002,2005). Thus, we
can provide approximation algorithms that do not rely on the ellipsoid
algorithm. Our methods can be extended to other combinatorial
optimization problems with submodular penalties. The talk will not
assume specific technical background.
This is joint work with Kiyohito Nagano from the University of Tokyo
and appeared in SODA 07.
Bio:
|
1:30pm, April 11, 2008 (Friday)
|
|
Chandra Chekuri
University of Illinois, Urbana-Champaign
|
Title: Approximation Algorithms for Disjoint Paths and Routing Problems
Abstract:
Click to hide abstract
A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a graph G=(V,E) and a set of pairs of vertices (s_1,t_1), (s_2,t_2), ..., (s_k,t_k). The objective is to decide if all the pairs can be connected by edge-disjoint paths. This problem is NP-Complete. We study approximation algorithms for MEDP, the optimization version of EDP in which the goal is to maximize the number of pairs that can be connected (routed).
We consider a natural multicommodity flow relaxation for MEDP and its integrality gap in undirected graphs. A simple example shows that the integrality gap of the flow relaxation is \Omega(\sqrt{n}) even in planar graphs; here n is the number of nodes in the graph. It has been conjectured that the integrality gap is much smaller if we relax the problem and allow some small number of paths to share an edge. We give an overview of a new framework and several results that followed from it, including an essential resolution to the above conjecture in planar graphs. The emphasis of the talk will be on high-level ideas and connections between work in theoretical computer science, optimization and graph theory.
Based on joint work with Sanjeev Khanna (Univ. of Pennsylvania) and Bruce Shepherd (McGill Univ.).
Bio:
Click to hide bio
Chandra Chekuri is an Associate Professor of Computer Science at University of Illinois at Urbana-Champaign (UIUC). He came to UIUC in the fall of 2006 after spending close to eight years as a research staff member at Lucent Bell Labs. At Bell Labs he contributed to several projects including wireless and optical network design that were recognized by Lucent for their technical and business impact. He obtained a PhD from Stanford University in 1998 and was a co-winner of the Arthur Samuel thesis award from the Computer Science department in 1999. His undergraduate degree is from Indian Institute of Technology, Madras (now Chennai). His research interests are in algorithms, combinatorial optimization, and applications with a focus on approximation algorithms for NP-Hard problems.
|
1:30pm, April 28, 2008 (Monday)
|
|
Santosh Kabadi
University of New Brunswick
|
Title: A Strongly Polynomial, Combinatorial Algorithm for Integer Version of
the Multipath Flow Network Synthesis Problem
Abstract:
Click to hide abstract
We consider the following integer, multipath flow network synthesis
problem. We are given two positive integers q, n, (1 < q < n), and a nonnegative,
integer, symmetric, nxn matrix R, each non-diagonal element r_ij of
which represents the minimum requirement of q-path flow value between
nodes i and j in an undirected network on the node set N={1,2,...,n}. We
want to construct a simple, undirected network G=[N,E] with integer edge
capacities {u_e :e in E} such that each of these flow requirements can be
realized (one at a time) and the sum of all the edge-capacities is minimum.
We present an O(n^3) combinatorial algorithm for the problem and we show
that the problem has integer rounding property.
Bio:
Click to hide bio
SANTOSH N. KABADI joined the Faculty of
Business Administration in 1985 and is a
member of the Quantitative Methods
area. He teaches Quantitative Analysis and
Statistical Techniques for Business in the
BBA program and Business Data Analysis and
Research Methods in the MBA
program. Dr. Kabadi received the UNB Merit
Award in 2002 for his performance in
research, service, and teaching. He
received the Faculty of Business
Administration's Excellence in Research
Award in 2001 and 2006 for outstanding
performance across his career. He also
received the UNBF MBA Society's Professor
Recognition Award in 2002.
|
1:30pm, May 9, 2008 (Friday)
|
|
Seyed Vahab Mirrokni
Microsoft
|
Title: Submodular Maximization, Marketing over Social Networks and More
Abstract:
Click to hide abstract
Submodular maximization is a central problem in optimization with many
applications in data mining, social network analysis,
and online advertisement. Unlike the problem of minimizing submodular
functions, the problem of maximizing submodular functions is NP-hard.
We design the first constant-factor approximation algorithms for maximizing
Non-negative submodular functions.
In particular, we give a deterministic local search 1/3-approximation and a
randomized 2/5-approximation algorithm for maximizing non-negative
submodular
functions. Furthermore, we prove that achieving an approximation factor
better than 1/2 requires exponential time.
Then, I will discuss applications of submodular maximization in the growing
field of the online advertisement, and in particular two specific
applications in marketing digital goods over social networks,
and revenue maximization for guaranteed banner advertisement. The first
application is concerned with viral marketing and word-of-mouth advertising
in social networks.
The second application is related to the banner ad allocation problem
satisfying a guaranteed delivery property.
The main part of the talk is based on joint work with Feige and Vondrak
(FOCS 2007), Hartline and Sundararajan (WWW 2008), and
Feige, Immorlica, and Nazerzadeh (WWW 2008).
Bio:
Click to hide bio
Seyed Vahab Mirrokni received his PhD in
Theoretical Computer Science from
Massachusetts Institute of Technology
under supervision of Professor Michel
Goemans. Prior to joining Microsoft
Research, he was a Postdoctoral Associate
in the Theory of Computation Group at MIT
Computer Science and AI Laboratory. He was
also holding a research scientist position
in the strategic planning and optimization
group at Amazon.com. During his PhD
studies, he worked at Microsoft theory
group , visited the theory of computation
group in IBM T.J. Watson research center,
and worked as an intern at Networking
Research Lab. of Bell-Laboratories and
visited Fundamental Mathematics Department
at Bell-Labs.
|
1:30pm, May 21, 2008 (Wednesday)
|
|
|
|