BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Sentry Selection - Balister\, PN (University of Memphis)
DTSTART:20100517T150000Z
DTEND:20100517T160000Z
UID:TALK24933@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Suppose we have a collection of sensors in a large region\, ea
 ch of which can detect events within a disk of radius 1. We wish to devise
  a schedule so that each sensor can sleep for much of the time\, while mak
 ing sure that the whole region is covered by the sensors that are awake. A
  natural way of doing this is to partition the sensors into k subsets\, ea
 ch subset of sensors covering the whole region. Then in time slot t we act
 ivate all the sensors in subset (t mod k). If this is possible we say the 
 sensors are k-partitionable. An obvious necessary condition is that each p
 oint in the region is covered by at least k sensors (k-coverage)\, but thi
 s is not in general sufficient. We show that for random deployments of sen
 sors k-coverage usually implies k-partitionability\, and identify the most
  likely obstructions to k-partitionability when this fails. This leads to 
 some natural unsolved problems involving k-partitionability of (determinis
 tic) configurations of disks. Joint work with B. Bollobas\, A. Sarkar\, an
 d M. Walters.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR