[Colloq] PhD Thesis Proposal

[Chantal Cardona]

SPEAKER: Guolong Lin
TIME: Thursday, Nov 10, 10AM
PLACE: 366 West Village H
TITLE: New paradigms and approximation algorithms for optimization
       under uncertainty

Abstract:
Combinatorial optimization problems arise frequently in many applied
fields such as communication network design, production planning and
information retrieval. Many of the interesting ones are NP-hard, which
means it is unlikely that there exist efficient algorithms to exactly
solve them.

In the context of classical combinatorial optimization, the inputs are
typically fixed and known. Many real-world applications, however, may
contain data parameters that are either unknown or subject to some
uncertainty. In this proposal, we study approximation algorithms for
combinatorial optimization problems with uncertainty. In particular,
we introduce and study two new paradigms of optimization under
uncertainty: universal optimization and incremental optimization. 

To illustrate the universal optimization model, consider the data
aggregation problem in sensor networks, where sensors collecting field
data need to route packages to some central entity. Different subsets
of the sensors may collect different types of data. For ease of
routing, one may ask if there is a single aggregation tree rooted at
the central entity, such that for any subset of the sensors, the
aggregation cost along the tree is close to the best achievable. Here,
the construction of the tree is oblivious to the uncertain subset that
need to be served. The incremental optimization model can be
illustrated by the k-median problem, where one asks for the opening of
at most k facilities to serve a given set of clients with minimum
total cost. If the number of facilities allowed is uncertain, one
question is, does there exist a sequence of the facilities to be
opened, so that, for any value of k, opening the first k facilities
will incur a service cost close to the best possible?

In the talk, we will define the paradigms, present some results
obtained so far and discuss future research directions.

Thesis proposal committee:
Rajmohan Rajaraman, Advisor
Guevara Noubir, Co-advisor
Jay Aslam
Agnes Chan
Greg Plaxton, University of Texas, Austin
Ravi Sundaram