CENTER Carnegie Mellon UniversityCarnegie Mellon Computer Science DepartmentSchool of Computer Science
Workshop on Flexible Network Design
Related Activities
Outreach Roadshow

November 4-5, 2005
Princeton University, Princeton, NJ
Small Auditorium (Room 105) - Computer Science Department

Online Registration Form

This workshop is organized under the auspices of the NSF ITR-funded ALADDIN Center, in which this is the first meeting of a PROBlem-oriented Exploration (or PROBE) on the topic. Network Design with its many variants is one of the most active mathematical research areas involving researchers from Theoretical Science, Graph Theory, Operations Research, Discrete Optimization, Game Theory and Information Theory. In addition, new problems in this area are constantly propounded by practitioners working in various aspects of network design such as construction, routing and staged deployment. Furthermore, many new design paradigms such as ATM, Ad Hoc and Wireless networking add rich new flavors to existing problems. The goal of this PROBE is to focus on this active area of applications of algorithms to understand current trends, identify understudied areas, and formulate new directions for further investigation. To this end, the PROBE will solicit participation from a sufficiently eclectic mix of experts from real-world network design and deployment, graph algorithms, network coding, algorithmic mechanism design applied to pricing problems in networks, and configuration and routing of networks.

Matthew Andrews, Bell Labs
Moses Charikar, Princeton University
Anupam Gupta, Carnegie Mellon University
Stefano Leonardi, Università di Roma "La Sapienza"
R. Ravi, Carnegie Mellon University


Registration: Susan Hrishenko, Carnegie Mellon University, Tel 412-268-7317.
Travel and Accommodations: Mitra Kelly, Princeton University, Tel 609-258-4562.

Registration Information
Registration is required. Anyone planning to attend the workshop (including Princeton and Carnegie Mellon faculty and students) should register online. There is no fee to attend this workshop. For questions about registration, please contact Susan Hrishenko, Carnegie Mellon University, Tel 412-268-7317.
Online Registration Form

Hotel Accommodations
The workshop hotel is AmeriSuites, 3565 US Highway 1, Princeton, NJ 08540 ( To take advantage of the pre-negotiated rate of $119 per night ($135.66 including 14% taxes), you should contact Monica Hannah in the sales office of the AmeriSuites directly at 609-720-0200 to make your reservations. Please be sure to ask for the Princeton Workshop meeting rate. Since the deadline for our block of rooms has passed, the AmeriSuites will still honor the workshop rate, but cannot guarantee availability. You can also try the Nassau Inn, 10 Palmer Square East, Princeton, NJ 08542, phone 609-921-7500. The Nassau Inn is closer to the department, but did not have any availability as of 11/1/05. For questions about local arrangements, please contact Mitra Kelly, Princeton University, Tel 609-258-4562.

Ground Transportation
Airport to AmeriSuites via Ride NJ Pass: You may use Ride NJ Pass from Philadelphia or Newark airports to Amerisuites for $25.00 each way during scheduled service hours. Advance reservations are required; to schedule your seat, call within 24 hours 1-877-FLY-NJPA (1-877-359-6572) or 609-635-3758 (let the phone ring). If you have questions once you arrive at the Philadephia, you can dial #34 at a courtesy phone station to reach them. For more details, please visit
Airport to Princeton via Other Methods: For more information about ground transportation from the airport to Princeton, please refer to
AmeriSuites to Workshop: A shuttle will be arranged to transport attendees between the AmeriSuites and the workshop.

Metered Parking: Attendees who arrive early (prior to 8:00 am) may park on Olden, William or Prospect street at the ten-hour meters. Please be sure to bring change and ensure that you park at a ten-hour meter (not a two-hour meter).
Campus Lot and Garage Parking: Visitors planning to park in lots and garages on campus should print and display the following parking permit on their dashboards:
Parking permit (pdf)
On Friday, visitors should park in Lot 21, then take the free campus shuttle to the E-Quad across the street from the Computer Science Deparment. (The driver can tell you where that is if you ask.) On Saturday, visitors may park in Parking Garage 3.
Campus map including parking areas (offsite link to

Expense Reimbursement for Invited Participants
Invited participants who were offered financial support should submit their original receipts along with an expense reimbursement form to Mitra Kelly, Princeton University, Computer Science Department, 35 Olden Street, Princeton, NJ 08544, Tel 609-258-4562. You should complete only the top section of the form with the "Pay To" information, then sign and print your name at the bottom where it says "Signature of Traveler" and "Print Name." Mitra will use the receipts you submit to complete the middle section in compliance with Princeton University accounting standards.
Non-employee travel voucher (pdf)

Agenda     Read the Abstracts    See the Poster (gif 147KB) (pdf 9.5MB)
Friday, November 4, 2005    Saturday, November 5, 2005
8:30 am Continental Breakfast
9:15 am

Jennifer Rexford, Princeton University
A Routing Control Platform for IP Networks (abstract)

9:45 am

Harald Räcke, Toyota Technological Institute at Chicago
Oblivious Network Design (abstract)

10:15 am Break
10:40 am

Anant Balakrishnan, University of Texas at Austin
Cutting Plane Approach for Service Network Design (abstract)

11:10 am

Dan Bienstock, Columbia University
Title TBD

11:40 am

Lisa Fleischer, IBM T J Watson Research Center
Title TBD

12:10 pm Lunch
1:00 pm

Open Problems

1:30 pm

Adrian Vetta, McGill University
Metric Design with Network Costs (abstract)

2:00 pm

Lisa Zhang, Lucent Technologies Bell Labs
Design for Optical Transparency (abstract)

2:30 pm

Nick Harvey, MIT
Network Coding: A New Direction in Combinatorial Optimization (abstract)

3:00 pm Break
3:30 pm

Iraj Saniee, Bell Labs Research
Load Balancing in CDMA Networks: A Distributed Dual Optimization Approach (abstract)

4:00 pm

Guido Schäfer, Technische Universität Berlin
A Tight 4.66-Approximation for Multicommodity Rent-or-Buy (abstract)

4:30 pm -
5:00 pm

Chaitanya Swamy, Caltech
Approximation Algorithms for Stochastic Optimization (abstract)

Saturday, November 5, 2005   Friday, November 4, 2005
8:30 am Continental Breakfast
9:30 am

Mohammad Mahdian, Microsoft Research
Title TBD

10:00 am

Joseph Cheriyan, University of Waterloo
On packing Steiner trees and related problems (abstract)

10:30 am Break
10:50 am

Thierry Klein, Lucent Technologies Bell Labs
Dynamic optimizations for next-generation wireless networks (abstract)

11:20 am

Sanjeev Khanna, University of Pennsylvania
Edge Disjoint Paths: On the Integrality Gap of the Multicommodity Flow Relaxation (abstract)

11:50 am

Christian Scheideler, Johns Hopkins University
Towards a paradigm for robust distributed algorithms and data structures (abstract)

12:20 pm Lunch
1:10 pm

Kamal Jain, Microsoft Research
Title TBD

1:40 pm

Tim Roughgarden, Stanford University
Title TBD

2:10 pm -
2:40 pm

MohammadTaghi Hajiaghayi, CSAIL - MIT
Graph Algorithms for Wireless Networks (abstract)


This material is based upon work supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation