[Colloq] PhD Thesis Defense, Guolong Lin - Monday, April 10, 2pm

[Rachel Kalweit]

College of Computer and Information Science
PhD Thesis Defense:
Guolong Lin

Thesis Title:
New paradigms and approximation algorithms for optimization under 
uncertainty

Monday, April 10, 2006
2:00pm
366 West Village H

Abstract
Combinatorial optimization problems arise frequently in diverse 
application areas 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 dissertation, we study approximation algorithms for 
combinatorial optimization problems with uncertainty. We introduce and 
study two new paradigms of optimization under uncertainty. The first 
paradigm is universal optimization, where, although there could be 
exponentially many different subinstances, we ask for a single solution 
from which one can efficiently derive a good approximate solution to any 
subinstance. The second paradigm is incremental optimization in which 
there is a benefit parameter k whose value is uncertain. Our goal is to 
construct a sequence of solution elements, such that given any value of 
k, one can quickly identify a prefix of the sequence, which forms a good 
approximate solution for the given k. Finally, we study a multiprocessor 
scheduling problem in which there is uncertainty concerning the 
successful execution of a job on a given processor.

In this talk, we will first outline the main results of the 
dissertation, and then focus on the problem of multiprocessor scheduling 
under uncertainty, which has applications in grid computing. In this 
problem, we are given n unit-time jobs and m machines, with precedence 
constraints among the jobs. For every job j and machine i, we are also 
given p_{ij}, which is the probability that job j when scheduled on a 
machine i will be successfully completed.  Multiple machines can be 
assigned to the same job at the same time. The goal of the problem is to 
find a schedule such that the expected completion time of all the jobs 
is minimized. We will present a polynomial time polylogarithmic 
approximation algorithm for the problem.


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