Colloquia, Seminars and Conference News
Title : Bin Packing with Deadlines
Date : November 2, 2005. (1:00 pm) Tea starts half an hour before each seminar
Location: ITEB 336
Speaker : Piotr Berman
Abstract:
We are given a set of items, each with its weight, arrival date and deadline, and we have to pack each item into a bin after it arrives but before the deadline. We describe factor 3 approximation algorithm, and factor 1.5 approximation algorithm for the case when each difference between a deadline and the corresponding arrival time is the same.
The original motivation is to find a minimal set of directional antennas placed on a single beacon that provide communication to a given set of customers. Each antenna can provide connections to customers within certain angle. In turn, customers have bandwidth requirements and customers allocated to one antenna cannot exceed its transmission capacity. We have factor 1.5 approximation for the case when every antenna has the same angle, and factor 3 when the angle of an antenna is a decreasing function of the maximum distance of a customer it can reach.
Joint work with Jieun Jeong, Shiva Kashisubrahmanian and Bhuvan
Urgaonkar. (Work in progress)
Bio:
Berman joined the Department of Computer Science and Engineering, The Pennsylvania State University in September 1982. His earlier education took place in Poland, where he received his master's degree from the Department of Mathematics and Computer Science, Uniwersytet Warszawski (University of Warsaw). He pursued further graduate research at Instytut Matematyczny PAN (Mathematics Institute of the Polish Academy of Sciences) prior to coming to the United States to study for his doctorate at MIT. Currently, Dr. Berman is working on theoretical issues of distributed systems and approximation algorithms. In general, he is interested in the theory of algorithms and its applications in other areas of computer science, such as distributed databases and biological computing.
