When: Friday, February 17, 12:00 p.m.
Where: 1507 Newell-Simon Hall
Andreas Krause
Abstract:
When monitoring spatial phenomena with wireless sensor networks, selecting the best sensor placements is a fundamental task. Not only should the sensors be informative, but they should also be able to communicate efficiently. In this talk, I will present our data-driven approach that addresses the three central aspects of this problem: measuring the predictive quality of a set of sensor locations (regardless of whether sensors were ever placed at these locations), predicting the communication cost involved with these placements, and designing an algorithm with provable quality guarantees that optimizes the NP-hard tradeoff. Specifically, we use data from a pilot deployment to build non-parametric probabilistic models called Gaussian Processes (GPs) both for the spatial phenomena of interest and for the spatial variability of link qualities, which allows us to estimate predictive power and communication cost of unsensed locations. Using these models, we present a novel efficient algorithm, pSPIEL, which selects Sensor Placements at Informative and cost-Effective Locations. Exploiting two important properties of this problem — submodularity and locality — we prove strong approximation guarantees for our pSPIEL approach. We also provide extensive experimental validation of this practical approach on several real-world placement problems, demonstrating significant advantages over existing methods.
Ryan O’Donnell, MIT/Microsoft Theory Group
Feb 20, 2006
NSH 3305, 1:30pm
Abstract:
For most constraint satisfaction problems — such as finding the maximum cut in a graph, or trying to solve an overconstrained system of equations — it is NP-hard to find an optimal solution. Nevertheless, one still wants to find algorithms that come as close to the optimum as they can. Unfortunately, the best known algorithms and the best known NP-hardness results do not yet match for many basic problems.
In this talk I will talk about recent attempts to find the sharp boundaries between P and NP for approximating constraint satisfaction problems. Interestingly, progress on proving hardness results mostly comes by finding more efficient algorithms in the area of “property testing”. I will describe new such algorithms and mention how their analysis is connected to such diverse areas as voting theory and the “double bubble” problem. As an example consequence of these connections, we get complexity-theoretic evidence that there is no efficient algorithm for finding the maximum cut in a graph with guarantee better than Goemans-Williamson’s: 0.878567….
BIO: Ryan O’Donnell received his Ph.D. from MIT in 2003, advised by Madhu Sudan. He then went to the Institute for Advanced Study as a postdoc under Avi Wigderson and is currently a postdoc at Microsoft Research. Ryan received a Best Student Paper award at CCC for his paper “Hardness amplicification within NP” and a Best Paper award for his paper “Extremal properties of polynomial threshold functions”. His research focus is on complexity theory, hardness of approximation, discrete fourier analysis, and computational learning theory.
Bert Zwart, Eindhoven University of Technology
NSH 3305, 1:30PM
Abstract:
Processor Sharing (PS) queues were originally introduced to analyze the performance of time-sharing in computer networks. Nowadays, PS queues are one of the most popular congestion models for TCP traffic on the Internet. Under the PS discipline, each customer in the system receives the same service rate.
Motivated by obtaining a better understanding of the impact of reneging (e.g. aborting the download of a file) in communication networks, we consider a PS queue in overload where customers may leave after a certain amount of time, before their service is finished. Under the PS service discipline, such behavior is unwelcome, since it always implies that some work is done in vain. Therefore, when the queue is in overload, the actual throughput can be much lower than the total service rate.
We consider a fluid approximation of this queue, which is accurate when both the arrival and service rates are large. We apply this fluid approximation to analyze the impact of reneging on system performance in PS queues. By studying several examples, we show that the impact can be quite substantial and propose an admission control scheme to reduce its effect.
BIO:
Bert Zwart received his Ph.D at Eindhoven University of Technology in september 2001 under the supervision of Onno Boxma and Sem Borst. After that, he did a postdoc at INRIA Rocquencourt (France). In 2002, Bert returned to Eindhoven as an assistant professor. Bert is currently associate editor of Mathematics of Operations Research and serves as TPC member in several conferences.His current research focuses on various topics in applied probability and the performance analysis of computer and communication systems.
