News Archives

[Colloquium] Randomized Rounding for Sensor Placement Problems

September 14, 2007

Watch Colloquium: 


  • Date: Friday, September 14th, 2007 
  • Time: 1 pm — 2:30 pm 
  • Place: ME 218

Cynthia Phillips 
Sandia National Laboratories

Abstract: The recent emphasis on homeland security in the U. S. has led to a number of new applications involving sensor placement in physical networks. We will describe some of these sensor placement problems including sensor placement in municipal water networks to minimize health effects from contamination and sensor placement for intruder detection in transportation networks or buildings. We have addressed these problems using (parallel) integer programming. In this talk we present a parallelizable heuristic method for finding approximate solutions to general sensor placement problems.

An Integer program (IP) is the optimization (maximization or minimization) of a linear function subject to linear constraints and integrality constraints on some or all of the variables. IPs naturally model NP-hard combinatorial optimization problems. Thus integer programming is itself NP-complete, but one can frequently solve instances in practice using branch and bound via commercial or research solvers. Removing the integrality constraints gives the linear-programming relaxation of an integer program. This is tractible both theoretically and in practice.

In this talk, we consider finding heuristic solutions to sensor placement IP problems using randomized rounding. This technique was introduced by Raghavan and Thompson. In its simplest form, one selects binary variables randomly independently using the LP-relaxation value as a probability distribution. For an arbitrary integer program, this will rarely find a solution that satisfies the linear constraints. However, our sensor-placement problems have only one hard constraint: a bound on the number of sensors. Other constraints compute the objective value.

We will present a new randomized rounding strategy that satisfies a single cardinality constraint. It samples uniformly from the set of “lucky” randomized roundings that happen to select exactly the correct number of variables. The algorithm requires O(k(n-k)) deterministic serial preprocessing time. We can then select a sensor placement with a small number of random numbers and O(n + k) additional time.

We compare our algorithm to a randomized rounding algorithm due to Doerr. His algorithm is also fast, meets the cardinality constraint, and has sufficient independence to allow Chernoff bound analysis. However, its implementation presents some challenging numerical issues. Our algorithm has stronger independence and a fundamentally different probability distribution for individual variables.

(Joint work with Jonathan Berry, Sandia National Laboratories)

Bio: Cindy Phillips is a Distinguished Member of the Technical Staff in the Algorithms and Discrete Math Department at Sandia National Laboratories. She received a B.A. in applied mathematics from Harvard University in 1983 and a PhD in computer science from MIT in 1990. She joined Sandia National Laboratories in 1990 where she has conducted research in combinatorial optimization, algorithm design and analysis, and parallel computation with applications to scheduling, network and infrastructure surety, integer programming, graph algorithms, vehicle routing, computational biology, and experimental algorithmics. She is one of three main developers of the PICO massively-parallel integer programming code. She was a member of the Compute Process Allocator (CPA) team that won an R&D 100 award in 2006.