Lisa Zhang

   600 Mountain Avenue, 2C-519 
   Murray Hill, NJ 07974 

   Tel.: +1 (908) 582-5281 
   Fax: +1 (908) 582-3340
   E-mail: ylz@research.bell-labs.com

Employment

  • Member of Technical Staff in Algorithms Research at Bell Laboratories, Lucent Technologies.

    • Education

  • Massachusetts Institute of Technology.  PhD in Applied Mathematics, 1997.

    •     Advisor: Professor Tom Leighton.
        Thesis: An Analysis of Network Routing and Communication Latency. ps.gz
     
  • Wellesley College. summa cum laude, BA in Mathematics and Computer Science, 1993.

    • Short bio

                I grew up in Shanghai China, finishing my highschool education there. I arrived in America in the summer of 1989 and spent the next eight years in the Boston area, first studying at Wellesley College then at MIT. In 1997 I joined Bell Labs in Murray Hill, NJ, and I have been working and living in New Jersey since. Before long I will have spent more time in America than in China.
                My research broadly concerns algorithmic and complexity issues of networking, which includes network planning and optimization, routing and scheduling protocols, and stability and Quality-of-Service analysis. My work is interdisciplinary, covering topics in theoretical computer science, applied mathematics, operations research and electrical engineering. More details are in my cv.
               

    Papers



    2008

  • Efficient Scheduling Algorithms for Real-Time Multicast Services in Wireless LANs. IEEE INFOCOM Mini Symposium 2008. Coauthored with Y. Bejerano, D. Lee and P. Sinha.

  • Satisfying Arbitrary Delay Requirements in Multihop Networks. IEEE INFOCOM 2008. Coauthored with M. Andrews.

  • Creating Templates to Achieve Low Delay in Multi-Carrier Frame-Based Wireless Data Systems. IEEE INFOCOM 2008. Coauthored with M. Andrews.


    • 2007

  • Buy-at-Bulk Network Design with Protection. IEEE FOCS 2007. Coauthored with S. Antonakopoulos, C. Chekuri and B. Shepherd. pdf.

  • Scheduling Algorithms for Multi-Carrier Wireless Data Systems. ACM Mobicom 2007. Coauthored with M. Andrews. pdf.

  • Heuristics for Fiber Installation in Optical Network Optimization. Proceedings of IEEE GLOBECOM 2007. Coauthored with S. Antonakopoulos.

  • Scheduling Algorithms for Single-Carrier and Multi-Carrier Wireless Data Systems. Allerton 2007, invited paper. Coauthored with M. Andrews.

  • A Note on Generalized Rank Aggregation. International Network Optimization Conference (INOC) 2007. Coauthored with H. Shachnai and T. Matsui.

  • Hardness of the Undirected Congestion Minimization Problem. SIAM Journal of Computing 37(1):112-131, 2007. Coauthored with M. Andrews.

  • Routing and Scheduling in Multihop Wireless Networks with Time-Varying Channels. ACM Transactions on Algorithms 3(3):Article 33, 2007. Coauthored with M. Andrews.


    • 2006

  • Logarithmic Hardness for the Directed Congestion Minimization Problem. ACM STOC, 2006. Coauthored with M. Andrews. pdf.

  • Admission Control for Multihop Wireless Backhaul Networks with QoS Support . IEEE Wireless Communications and Networking Conference, 2006. Coauthored with S. Lee, G. Narlikar, M. Pal and G. Wilfong.

  • Designing Multihop Wireless Backhaul Networks with Delay Guarantees . IEEE INFOCOM, 2006. Coauthored with G. Narlikar and G. Wilfong. pdf.

  • Complexity of Wavelength Assignment in Optical Network Optimization. IEEE INFOCOM, 2006. Coauthored with M. Andrews. pdf.

  • Minimizing Maximum Fiber Requirement in Optical Networks. Journal of Computer and Systems Sciences 72:118-131, 2006. Coauthored with M. Andrews. pdf.

  • Scheduling Over Non-Stationary Wireless Channels with Finite Rate Sets . IEEE/ACM TON 14(5):1067-1077, 2006. Coauthored with M. Andrews. pdf.

  • Logarithmic Hardness of the Undirected Edge-Disjoint Paths Problem. . JACM 53(5):745-761, 2006. Coauthored with M. Andrews.

  • Design Tools for Transparent Optical Networks . Bell Labs Technical Journal 11(2):129-143, 2006. Coauthored with C. Chekuri, P. Claisse, R. Essiambre, S. Fortune, D. Kilper, W. Lee, K. Nithi, I. Saniee, B. Shepherd, C. White and G. Wilfong. doc.

  • A Tool for CDMA Data Measurement and Analysis. Proceedings of the Second International Workshop On Wireless Network Measurement, 2006. Coauthored with M. Andrews.

    • 2005

  • Scheduling over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data. Journal of the ACM 52(5): 809-834, 2005. Coauthored with M. Andrews. pdf.

  • Source Routing and Scheduling in Packet Networks. Journal of ACM 52(4): 582-601, 2005. Coauthored with M. Andrews, A. Fernandez and A. Goel. pdf.

  • Hardness of the Undirected Edge Disjoint Path Problem with Congestion. IEEE FOCS, 2005. Coauthored with M. Andrews, J. Chuzhoy and S. Khanna.

  • The Master Ring Problem. International Conference on Analysis of Algorithms, 2005. Coauthored with H. Shachnai. pdf.

  • Hardness of the Undirected Congestion Minimization Problem. ACM STOC, 2005. Coauthored with M. Andrews. pdf.

  • Hardness of the Undirected Edge Disjoint Paths Problem. ACM STOC, 2005. Coauthored with M. Andrews. pdf.

  • Bounds on Fiber Minimization in Optical Networks. IEEE INFOCOM, 2005. Coauthored with M. Andrews. ps.

  • The New Paradigm for Wireless Network Optimization: A Synergy of Automated Processes and Human Intervention. . IEEE Communications Magazine 43(3), 2005. Coauthored with G. Hampel, D. Abush-Magder, A. Diaz, L. Drabeck, M. Flanagan, J. Graybeal, J. Hobby, M. MacDonald, P. Polakos, J. Srinivasan, H. Trickey and G. Rittenhouse.

    • 2004

  • Path Decomposition under a New Cost Measure. Proceedings of 12th Annual European Symposium on Algorithms (ESA). Bergen, Finland, September 2004. Coauthored with E. Anshelevich.

  • The Effects of Temporary Sessions on Network Performance. SIAM Journal on Computing 33(3): 659-673, 2004. Coauthored with M. Andrews.

  • Scheduling Protocols for Switches with Large Envelopes. Journal of Scheduling 7(3): 171-186, 2004. Coauthored with M. Andrews.

  • Minimizing End-to-End Delay in High-Speed Networks with a Simple Coordinated Schedule. Journal of Algorithms 52(1): 57-81, 2004. Coauthored with M. Andrews.

  • Wavelength Assignment in Optical Networks with Fixed Fiber Capacity. Proceedings of 31st International Colloquium on Automata, Languages and Programming (ICALP). Turku, Finland, July 2004. Coauthored with M. Andrews.

  • Line System Design for DWDM Networks. Proceedings of the 11th International Telecommunications Network Strategy and Planning Symposium (Networks). Vienna, Austria, June 2004. Coauthored with S. Fortune and W. Sweldens.

  • DCM Selection on an Optical Line System. Proceedings of the 11th International Telecommunications Network Strategy and Planning Symposium (Networks). Vienna, Austria, June 2004. Coauthored with C. Chekuri and W. Lee.

  • Scheduling over Non-stationary Wireless Channels. Proceedings of 2004 IEEE INFOCOM. Hong Kong, March 2004. Coauthored with M. Andrews.

  • Routing and Scheduling in Multihop Wireless Networks with Time-Varying Channels. Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). New Orleans, LA, January 2004. Coauthored with M. Andrews.

    • 2003

  • Optical Line System Configuration via Dynamic Programming. Proceedings of the International Network Optimization Conference (INOC). Paris, France, October 2003. Coauthored with C. Chekuri and W. Lee.

  • Achieving Stability in Networks of Input-Queued Switches. IEEE/ACM TON, 11(5):848 -- 857, 2003. Coauthored with M. Andrews.

  • Wavelength Assignment and Generalized Interval Graph Coloring. ACM-SIAM SODA, 2003. Coauthored with P. Winkler.

    • 2002

  • Fast Fair and Frugal Bandwidth Allocation in ATM Networks, Algorithmica special issue Internet Algorithms 33:272 -- 286, 2002. Coauthored with Y. Bartal, M. Farach-Colton and S. Yooseph.

  • New Algorithms for Disk Scheduling, Algorithmica 32:277-301 2002. Coauthored with M. Andrews and M. Bender.

  • Approximation Algorithms for Access Network Design, Algorithmica 34: 197 -- 215, 2002. Coauthored with M. Andrews.

  • Scheduling over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data, IEEE FOCS, 2002. Coauthored with M. Andrews.

  • The Performance of GPS and EDF with Temporary Sessions, IEEE International Workshop on Quality of Service, 2002. Coauthored with M. Andrews.

  • Scheduling Protocols for Switches with Large Envelopes, ACM-SIAM SODA, 2002. Coauthored with M. Andrews.

  • An Improved FPTAS for Restricted Shortest Path, Information Processing Letters, September 2002. Coauthored with F. Ergun and R. Sinha.

    • 2001

  • An Augmentation Algorithm for Mincost Multicommodity Flow on a Ring, Discrete Applied Mathematics 110:301 -- 315, 2001. Coauthored with B. Shepherd.

  • Source Routing and Scheduling in Packet Networks, Proceedings of the 42nd Annual IEEE Symposium on Foundation of Computer Science (FOCS), pp. 168 -- 177, Las Vegas NV, October 2002. Coauthored with M. Andrews, A. Fernandez and A. Goel.

  • Achieving Stability in Networks of Input-Queued Switches, Proceedings of IEEE INFOCOM 01, Anchorage Alaska, April 2001. Coauthored with M. Andrews.

  • General Dynamic Routing with Per-Packet Delay Guarantees, SIAM Journal on Computing 30(5): 1594 -- 1623, 2002. Coauthored with M. Andrews, A. Fernandez, M. Harchol-Balter and T. Leighton.

    • 2000

  • Blocking Estimates in a Partitioned-Sector TDMA System, Dial M for Mobility 2000: The 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 28 -- 34, Boston MA, August 2000. Coauthored with C. Chekuri, K. Ramanan and P. Whiting.

  • QoS Routing with Performance-Dependent Costs, Proceedings IEEE INFOCOM 00, pp. 137 -- 146, Tel Aviv Isreal, March 2000. Coauthored with F. Ergun and R. Sinha.

  • The Effects of Temporary Sessions on Network Performance, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 448 -- 457, San Francisco CA, January 2000. Coauthored with M. Andrews.

    • 1999

  • Improved Bounds for On-Line Load Balancing, Algorithmica 23(4):278-301 1999. Coauthored with M. Andrews and M. X. Goemans.

  • Automatic Methods for Hiding Latency for Parallel and Distributed Computing, SIAM Journal on Computing 29(2):615-647 1999, pp. 615 -- 647. Coauthored with M. Andrews, T. Leighton and P. T. Metaxas.

  • An Augmentation Algorithm for Mincost Multicommodity Flow on a Ring, Proceedings of IEEE GLOBECOM 1999, Rio de Janeiro Brazil, December 1999. Coauthored with B. Shepherd.

  • Packet Routing with Arbitrary End-to-End Delay Requirements, Proceedings of the 31st Annual ACM Symposium on Theory of Computation (STOC), pp. 557 -- 565, Atlanta GA, May 1999. Coauthored with M. Andrews.

  • Minimizing End-to-End Delay in High-Speed Networks with a Simple Coordinated Schedule, Proceedings of IEEE INFOCOM 99, pp. 380 -- 388, New York NY, March 1999. Coauthored with M. Andrews.

  • Fast Fair and Frugal Bandwidth Allocation in ATM Networks, Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 92 -- 101, Baltimore MD, January. Coauthored with Y. Bartal, M. Farach-Colton and S. Yooseph.

    • 1998

  • The Access Network Design Problem, Proceedings of the 39th Annual IEEE Symposium on Foundation of Computer Science (FOCS), pp. 40 -- 49, Palo Alto CA, November 1998. Coauthored with M. Andrews.

  • Stability Results for Networks with Input and Output Blocking, Proceedings of the 30th Annual ACM Symposium on Theory of Computation (STOC), pp. 369 -- 377, Dallas TX, May 1998. Coauthored with M. Andrews.

    • 1997

  • Efficient Execution of Nondeterministic Parallel Programs on Asynchronous Systems, Information and Computation 139(1):1--16 25 November 1997. Coauthored with Y. Aumann and M. Bender.

  • General Dynamic Routing with Per-Packet Delay Guarantees, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 294 -- 302, Miami Beach FL, October 1997. Coauthored with M. Andrews, A. Fernandez, M. Harchol-Balter and T. Leighton.

  • A Performance Comparison of Competitive On-Line Routing and State-Dependent Routing, Proceedings of IEEE GLOBECOM 97, Phoenix AZ, November 1997. Coauthored with W. Aiello, M. Andrews, S. Bhatt and K. R. Krishnan.

    • 1996

  • Improved Bounds for On-Line Load Balancing, Proceedings of the 2nd Annual International Conference on Computing and Combinatorics, pp. 1 -- 10, Hong Kong, June 1996. Coauthored with M. Andrews and M. X. Goemans.

  • New Algorithms for the Disk Scheduling Problem, Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), pp. 550 -- 559, Burlington VT, October, 1996. Coauthored with M. Andrews and M. Bender.

  • Efficient Execution of Nondeterministic Parallel Programs on Asynchronous Systems, Proceedings of the 8th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 270 -- 276, Padua Italy, June 1996. Coauthored with Y. Aumann and M. Bender.

  • Open Problems for Latency Hiding in High Bandwidth Networks, Proceedings of the 7th Australia Workshop on Combinatorial Algorithms, Australia, July 1996. Coauthored with M. Andrews, T. Leighton and P. T. Metaxas.

  • Improved Methods for Hiding Latency in High Bandwidth Networks, Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 52 -- 61, Padua Italy, June 1996. Coauthored M. Andrews, T. Leighton and P. T. Metaxas.

  • Automatic Methods for Hiding Latency in High Bandwidth Networks, Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 257 -- 265, Philadelphia PA, May 1996. Coauthored M. Andrews, T. Leighton and P. T. Metaxas.

    • sophie