[Colloq] Reminder: PhD Thesis Defense, Guolong Lin -Today, 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

_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq