Friday February 1st, 2008
11:00AM
1305 Newell-Simon Hall
Speaker: Ivet Bahar (University of Pittsburgh)
TITLE: Supramolecular Machinery: Insights from Elastic Network Models
ABSTRACT:
Many proteins function as molecular machines. Understanding the principles that control the machinery of biomolecular systems can be a challenge due to the involvement of multiple subunits and cooperative interactions manifested by allosteric changes in conformations beyond the range of atomic simulations. We have developed and utilized low resolution models to explore the collective dynamics of such complex systems, and to bridge structure and function, through the paradigm structure-encodes-dynamics-encodes-function. The elastic network models and methods we introduced to this aim have found utility in many applications and have helped us gain insights into the intrinsic, structure-encoded ability of native structures to energetically favor the reconfigurations between functional substates. An overview of these recent progresses will be presented, along with the application to a few systems.
Friday February 1st, 2008
Wean Hall 7220
3:30pm
Speaker: Jiri Sgall (Academy of Sciences of the Czech Republic)
Title: Preemptive Online Scheduling: Optimal Algorithms for All Speeds
Abstract:
In this talk, we describe an optimal online algorithm for a large class of scheduling problems.
We are interested in an online version of the classical problem of preemptive scheduling on uniformly related machines. We are given machines with different speeds and a sequence of jobs, each described by its processing time (length). The objective is to find a schedule of all jobs in which the maximal completion time (makespan) is minimized. In the preemptive version, each job may be divided into several pieces, which can be assigned to different machines in disjoint time slots. In the online problem, jobs arrive one-by-one and we need to assign each incoming job to some time slots on some machines, without any knowledge of the jobs that arrive later.
Our new algorithm is optimal for any fixed combination of speeds of the machine, and thus our results subsume all the previous work on various special cases. The algorithm is deterministic, yet it is optimal even among all randomized algorithms. Together with previous results and a new lower bound it follows that the overall competitive ratio of this optimal algorithm is between $2.054$ and $e \approx 2.718$. Finally, our algorithm can be extended into various semi-online settings, where some partial information about the input instance is known, e.g., the maximal processing time or the sum of all the processing times.
