Speaker: Dr. Lisa Zhang, Alcatel-Lucent Bell Labs, USA
Time: 10:30am—11:30am, August 18th, 2010 (Wednesday)
Place: Room 446, 4th Floor, ICT, CAS
Abstract: 
Energy consumption is a critical problem in modern computing and communication systems due to exponentially increasing energy costs. Different techniques have been developed to reduce energy consumption. A goal for potential energy saving in data networking is achieving energy proportionality.
In this talk we focus on network routing problem with the energy minimization. Given a network, a set of demands and a cost function , the min-cost network design problem is to route all demands with the objective of minimizing , where  is the total traffic load under the routing. We focus on cost functions of the form  for  . For  ,　 is subadditive and exhibits behavior consistent with economies of scale. This problem corresponds to the well-studied Buy-at-Bulk network design problem and admits polylogarithmic approximation and hardness. In this talk, we focus on the less studied scenario of , where the function  models energy consumption of certain computing and communication devices. If the startup cost , we show a constant approximation via a simple scheme of randomized rounding. The scenario is quite different when the startup cost  . For this case a constant approximation is no longer feasible. Instead we show a polylogarithmic approximation algorithm. We obtain this result by solving related problems such as a capacitated min-cost flow and low-congestion routing.
Bio:
Lisa Zhang is a member of technical staff in the Algorithms Research Group at Bell Labs in Murray Hill, NJ. She received her B.A., summa cum laude, in mathematics from Wellesley College in 1993 and her Ph.D. in Theory of Computing from the Massachusetts Institute of Technology in 1997. Her research area is algorithm design and analysis. Her research broadly concerns algorithmic and complexity issues of networking, with a focus on design and optimization, routing and scheduling protocols, and stability and Quality-of-Service analyses.  She twice won the Bell Labs President's Gold Award and the Lucent Chairman's Award. She has published over 80 papers in conferences including ACM STOC, IEEE FOCS, MOBICOM, INFOCOM and journals including J. ACM, IEEE/ACM Trans. on Networking. She has recently served on FOCS, SODA, SPAA and IPDPS.