“INTEGER PROGRAMMING, A TECHNOLOGY”
Anureet Saxena
Friday, May 4, 2007
1:30 pm
153 Posner Hall
Mixed Integer Programming addresses the problem of minimizing (or maximizing) a linear function over a set of linear constraints such that some or all of the decision variables are constrained to be integers. Over the last five decades, mixed integer programming has emerged as a formidable optimization technology and has thereby opened research avenues which did not exist before. This thesis examines some of these new research opportunities in the form of four essays.
Read the rest of this entry »
Title : Efficient Distributed Approximation Algorithms for Minimum Spanning Trees
Speaker : Gopal Pandurangan, Department of Computer Science, Purdue University
When : 4:30-5:30pm May 3rd
Where : PPB 300
ABSTRACT : The Minimum Spanning Tree (MST) problem is one of the most important and commonly occurring primitive in the design and operation of data and communication networks. There are almost optimal distributed algorithms for this problem. However, these algorithms require relatively large amount of communication or time, and are fairly involved; this makes these algorithms impractical for emerging technologies such as peer-to-peer and sensor networks. The focus of this talk is a very simple scheme called the Nearest Neighbor Tree (NNT) scheme for constructing an O(log n)-approximate MST in a weighted graph. We use the scheme to design efficient distributed approximation algorithms for the MST problem under various settings:
(1) A randomized variant of the scheme can be applied to design a communication-efficient distributed approximation algorithm in a complete weighted metric network. Our result shows that the expected communication complexity of our algorithm is significantly better than the best distributed algorithm that finds the MST.
(2) We show that our scheme can be used to construct a fast distributed MST approximation algorithm in arbitrary networks. Our algorithm is existentially optimal (up to polylogarithmic factors) with respect to both time and communication complexity. Significantly, our result also shows that there can be an exponential time gap between exact and approximate MST computation. Another consequence of our result is that an approximate MST in unit-disk graphs (which are popular models of wireless networks) and in random weighted networks can be found in almost optimal time.
(3) Our scheme can also be used in ad hoc wireless networks to construct low-energy spanning trees in a energy-efficient manner. For uniform distribution of nodes, we show that our algorithms give a constant approximation; we also show that the energy needed to construct these approximate spanning trees is within a constant factor of the minimum possible energy that is needed to construct the optimal energy tree. The time and communication complexities of our algorithms are nearly the best possible.
(Joint works with Maleq Khan and V.S. Anil Kumar.)
Friday May 4th, 2007
WEH 7220
3:30pm
Title: Testing properties of graphs and functions
Balazs Szegedy
University of Toronto
Abstract: We give an analytic approach to property testing and a new characterization for testable graph properties. This is a joint work with Laszlo Lovasz.
May 4, 2007
Adam Christopher Wierman
11:00 AM, 5409 Wean Hall
Thesis Oral
Title: Scheduling for Today’s Computer Systems: Bridging Theory and Practice
Abstract:
Scheduling is a fundamental technique for improving performance in computer systems. From web servers to routers to operating systems, how the bottleneck device is scheduled has an enormous impact on the performance of the system as a whole. Given the immense literature studying scheduling, it is easy to think that we already understand enough about scheduling. But, modern computer system designs have highlighted a number of disconnects between traditional analytic results and the needs of system designers. In particular, the idealized policies, metrics, and models used by analytic researchers do not match the policies, metrics, and scenarios that appear in real systems.
The goal of this thesis is to take a step towards modernizing the theory of scheduling in order to provide results that apply to today’s computer systems, and thus ease the burden on system designers. To accomplish this goal, we provide new results that help to bridge each of the disconnects mentioned above. We will move beyond the study of idealized policies by introducing a new analytic framework where the focus is on scheduling heuristics and techniques rather than individual policies. By moving beyond the study of individual policies, our results apply to the complex hybrid policies that are often used in practice. For example, our results enable designers to understand how the policies that favor small job sizes are affected by the fact that real systems only have estimates of job sizes. In addition, we move beyond the study of mean response time and provide results characterizing the distribution of response time and the fairness of scheduling policies. These result! s allow us to understand how scheduling affects QoS guarantees and whether favoring small job sizes results in large job sizes being treated unfairly. Finally, we move beyond the simplified models traditionally used in scheduling research and provide results characterizing the effectiveness of scheduling in multiserver systems and when users are interactive. These results allow us to answer questions about the how to design multiserver systems and how to choose a workload generator when evaluating new scheduling designs.
Thesis Committee:
Mor Harchol-Balter, Chair
John Lafferty
Bruce Maggs
Alan Scheller-Wolf
Ward Whitt, Columbia University
