
Abstracts 
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
Despite the early design goal of minimizing the complexity of network
elements, tremendous amounts of state and logic are distributed across
routers and management platforms in today's IP networks. The many,
looselycoordinated actors that create and manipulate the distributed
state make it extremely difficult for network operators to manage
their networks. Instead, we advocate moving the decision logic for
running the network from the individual routers into a separate
management platform, leaving routers simply to disseminate timely
information about the network and forward data packets based on
explicit instructions from the management system. In this talk, we
argue that this approach would simplify network management and enable
new services. Then, we describe a way to migrate to the new
networkmanagement architecture while remaining backwards compatible
with the installed base of IP routers. Experiments with our prototype
implementation show that a Routing Control Platform built from
commodity components is fast and reliable enough to select routes for
hundreds of routers in a large ISP network. We believe that this new
approach will enable muchneeded innovation in network management and,
ultimately, in the design of routers and switches as well.
This talk will draw on the papers listed at http://www.cs.princeton.edu/~jrex/netwide.html.

9:45 am 
Harald Räcke,
Toyota Technological Institute at Chicago
Oblivious Network Design
Consider the following network design problem: given a network
$G = (V,E)$, sourcesink pairs $\{s_i, t_i\}$ arrive and desire to
send a unit of flow between themselves. The cost of the routing is this: ifedge $e$ carries a total of $f_e$ flow (from all the terminal pairs), the cost is given by $\sum_e \load(f_e)$, where $\load$ is some
concave cost function; the goal is to minimize the total cost
incurred. However, we want the routing to be oblivious: when
terminal pair $(s_i, t_i)$ makes its routing decisions, it does not
know the current flow on the edges of the network, nor the identity of the other pairs in the system. Moreover, it does not even know the
identity of the function $\load$, merely knowing that $\load$ is a
concave function of the total flow on the edge. How should it
(obliviously) route its one unit of flow? Can we get competitive
algorithms for this problem?
We develop a framework to model oblivious network design problems
(of which the above problem is a special case), and give algorithms
with polylogarithmic competitive ratio for problems in this
framework (and hence for this problem).
This is joint work with Anupam Gupta and MohammadTaghi Hajiaghayi.

10:15 am 
Break 
10:40 am 
Anant Balakrishnan,
University of Texas at Austin
Cutting Plane Approach for Service Network Design
Many applications in transportation, telecommunications, and supply chain contexts require designing networks that are both costeffective and responsive. To model these situations, we consider the multicommodity network design problem of selecting the least cost set of edges containing origindestination routes that satisfy endtoend service requirements such as limits on total traversal time or reliability. This service network design problem generalizes previous models such as the budgetconstrained shortest path, light tspanner, and hopconstrained network design problems. We focus on developing effective optimizationbased solution methods that rely on strengthening the LPrelaxation of the model formulation. We describe several classes of valid inequalities for the problem, discuss separation routines, and report preliminary computational results using a cutting plane procedure incorporating these inequalities.

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
We study undirected networks with edge costs that satisfy the triangle inequality. We present an O(1)approximation algorithm for a generalization of the metriccost subset knodeconnectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edgeconnectivity version of the problem, where the requirements are for edgedisjoint paths rather than for openly nodedisjoint paths. A corollary is that, for metric costs and for each k=1,2,...,n1, there exists a knode connected graph whose cost is within a factor of 24 of the cost of any simple kedge connected graph.
Based on our O(1)approximation algorithm, we present an O(log rmax)approximation algorithm for the nodeconnectivity survivable network design problem where rmax denotes the maximum requirement over all pairs of nodes.

2:00 pm 
Lisa Zhang,
Lucent Technologies Bell Labs
Design for Optical Transparency
Optical transparency allows signal to travel within an optical network without electronic processing. In this talk we describe new models for designing transparent optical networks. We present recent theoretical advances as well as practical issues arising from design tools that we are developing at Bell Labs.
This work is joint with many colleagues from Bell Labs.

2:30 pm 
Nick Harvey,
MIT
Network Coding: A New Direction in Combinatorial Optimization
Network coding is a new research area that centers on a fundamental and practical question: How much data can be transmitted through a communication network? Computer scientists have traditionally addressed such questions using network flow theory or other combinatorial models. Network coding enhances these traditional approaches by allowing network nodes to encode and intermingle the data as it flows through the network. The resulting model is quite powerful and leads to many surprising results. There are many intriguing open questions in network coding, suggesting an interesting new direction for work in combinatorial optimization.
We survey some of the initial work in this area and present some recent results. First we will discuss network codes for multicasting data and algorithms for constructing such codes. Next we will consider scenarios where each data source transmits to a single sink node (as in multicommodity flows). For some directed graphs, we show that the use of network coding can allow data transmission at a much higher bandwidth. For undirected graphs, it is conjectured that network coding provides no bandwidth improvement at all. This conjecture turns out to have interesting connections to open problems in complexity theory. Using a blend of information theoretic and graph theoretic arguments, we give the first proof of this conjecture for a nontrivial class of graphs.
This is joint work with Micah Adler, Kamal Jain, David Karger, Robert Kleinberg, April Rasala Lehman, and Kazuo Murota.

3:00 pm 
Break 
3:30 pm 
Iraj Saniee,
Bell Labs Research
Load Balancing in CDMA Networks: A Distributed Dual Optimization Approach
We consider a linear programming (LP) model for balancing loads in a system of base stations in powercontrolled CDMA networks.
This LP characterizes the (theoretical) minimum achievable base station load for a given configuration of mobiles at a given time interval.
We next consider the dual formulation of this optimization problem, which turns out to incorporates the wellknown fixedpoint problem encountered in uplink power control in CDMA networks (and whose iterative solution is embedded in CDMA handsets).
While the solution of the LP offers valuable insight to the qualitative properties of the optimal power allocation, the dual model furnishes the critical notion that optimal power allocation need not only be based on signal strengths but also on the "shadow price" imputed from each base station. The dual model also provides the necessary mechanism for an iterative ascent scheme for solving the load balancing problem in a (mostly) distributed fashion with low communication overhead leveraging the fixedpoint scheme as a substep. Extensive numerical experiments demonstrate substantial scope for capacity gains from balancing base station loads even in conservative scenarios.
This is joint work with Sem Borst, Georg Hampel, and Phil Whiting.

4:00 pm 
Guido Schäfer,
Technische Universität Berlin
A Tight 4.66Approximation for Multicommodity RentorBuy
In the multicommodity rentorbuy network
design problem (MRoB) we are given a network
together with k terminal pairs (s_i, t_i). The
goal is to install capacities on the edges of the
network so that a prescribed amount of flow f_i
can be routed between all terminal pairs s_i and
t_i simultaneously. We can either rent capacity
on an edge at some cost per unit flow or buy
infinite capacity on an edge at some larger fixed
cost. The overall objective is to install
capacities at a minimum total cost.
Gupta et al. (FOCS '03) gave a randomized scheme
for the MRoB problem that has been used
subsequently to improve the approximation ratio
for this problem. The currently best known
6.82approximation algorithm is due to Becchetti
et al. (SODA '05).
We present a surprisingly simple primaldual
4.66approximation algorithm and show that this
result is tight; that is, no better approximation
ratio can be achieved using the above mentioned
randomized scheme in combination with the
currently best known approximation algorithms.
This is joint work with Lisa Fleischer, Jochen Könemann, and Stefano Leonardi.

4:30 pm  5:00 pm 
Chaitanya Swamy,
Caltech
Approximation Algorithms for Stochastic Optimization
Stochastic optimization provides a means to handle uncertainty where (part of) the input is specified in terms of a probability distribution over possible realizations of the data, instead of deterministic data given in advance. We consider the widelyused paradigm of stochastic recourse models where the uncertainty evolves through a series of stages and one can take decisions in each stage in response to the new information learned. Planning under uncertainty introduces several algorithmic challenges with even simple polynomialtime solvable deterministic problems becoming computationally intractable in the stochastic setting.
I will give an overview of some recent work on the design of approximation algorithms for these problems, most of which has focused on 2stage recourse problems: one makes some initial decisions given only distributional information about the data, then the actual data is realized and further recourse actions may be taken. If time permits, I will briefly talk about very recent work on multistage problems where the random data is sequentially instantiated in multiple stages and one can take recourse actions in each stage.
Some of the results I will talk about were obtained in joint work with David Shmoys.


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
A set of nodes of an undirected graph G is called kedge connected if there exist k edgedisjoint paths between every pair of nodes in the set. A conjecture of Kriesell states that if T is a 2kedge connected node set, then there exist k edgedisjoint Steiner trees with terminal set T. The talk will survey some recent progress on this conjecture and related topics, using methods from the design and analysis of approximation algorithms.
This is joint work with Mohammad Salavatipour.

10:30 am 
Break 
10:50 am 
Thierry Klein,
Lucent Technologies Bell Labs
Dynamic optimizations for nextgeneration wireless networks
We discuss the role of network performance optimization, which is required when deploying realworld wireless networks to adjust to complex channel propagation effects, network layout irregularities and inhomogeneous traffic distributions. Traditional and automated optimization procedures are presented, along with a cellular optimization tool to enhance the coverage and capacity of CDMA networks.
The emerging trends in wireless data networks naturally lead to dynamic network optimizations. To highlight these trends, the specific problem of autonomous base station deployment is presented in greater detail.
The objective of the optimization is to adjust the base station locations and the transmit powers to dynamic user distributions and changing network topologies.

11:20 am 
Sanjeev Khanna,
University of Pennsylvania
Edge Disjoint Paths: On the Integrality Gap of the Multicommodity Flow Relaxation
Edgedisjoint paths (EDP) is a fundamental problem in combinatorial optimization. We are given a network and a collection of sourcedestination pairs in the network. The goal is to route as many pairs as possible such that the paths assigned to the routed pairs do not share any network links.
A wellstudied approach for designing approximation algorithms for EDP is to use the multicommodity flow relaxation. It is known that the integrality gap of this relaxation is $\Omega(\sqrt{n})$ even in undirected planar graphs. It is also known that the gap is no worse than $O(n^{2/3})$ even in general graphs. In the first part of this talk, we will show that the integrality gap in general undirected graphs is $O(\sqrt{n})$, matching the known lower bound. In the second part, we will present some results on how the integrality gap changes when we allow congestion.
This is joint work with Chandra Chekuri (Bell Labs), Julia Chuzhoy (MIT and UPenn), and Bruce Shepherd (Bell Labs).

11:50 am 
Christian Scheideler,
Johns Hopkins University
Towards a paradigm for robust distributed algorithms and data structures
There is a wealth of literature on distributed algorithms and data structures. Standard models used in the research community are synchronous or asynchronous shared memory or network models. The shared memory model is basically a generalization of the von Neumann model from one processing unit to multiple processing units or processes acting on a single, linear addressable memory. In the network model, there is no shared memory. Every processing unit has its own, private memory, and the processing units are interconnected by a network of (usually) bidirectional communication links that allow the processing units to exchange messages. The set of processing units is usually considered to be fixed though processing units may fail and recover according to some stochastic or adversarial model.
With the rise of very large distributed systems such as peertopeer systems, these models are not appropriate any more. For example, the set of processing units can be highly dynamic and there may not be any mutual trust relationships between the units. This creates fundamental problems, such as keeping the (honest) units in a single connected component, that the previous models cannot address in their basic form. We show how to extend the network model so that we have a model that is powerful enough to design algorithms and data structures that are provably robust even against massive adversarial attacks. This model even allows to design strategies capable of addressing modern threats such as denialofservice attacks that appear to lie outside of the algorithms realm. Our hope is that this model will open up many interesting research problems in the areas of network theory and distributed algorithms and data structures in the future.

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,
MIT
Graph Algorithms for Wireless Networks
In this talk, we present realworld applications with deep theoretical underpinnings and consequences and show how wireless multihop Networks, algorithmic graph theory, and computational complexity have a nice intersection in this area.
We present logarithmic approximability and almostlogarithmic inapproximability for a maximization problem called "unique
coverage": given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. The unique coverage problem defined above is a natural maximization version of set cover which was brought to our attention from its applications in wireless networks.
In one (simplified) application, we have a certain budget to build/place some transmitters at a subset of a specified set of possible locations. Our goal is to maximize the clients that are "covered" by (i.e., are within the range of) exactly one transmitter; these are the clients that receive signal without interference. Specifically, we prove O(1/log^{sigma(epsilon)} n) inapproximability assuming that NP is not subseteq
BPTIME(2^{n^epsilon}) for some epsilon > 0. We also prove O(1/log^{1/3\epsilon} n) inapproximability, for any epsilon > 0, assuming that refuting random instances of 3SAT is hard on average.
We establish matching upper bounds up to exponents, even for a more general (budgeted) setting, giving an Omega(1/log n)approximation algorithm as well as an Omega(1/log B)approximation algorithm when every set has at most B elements. We also show that our inapproximability results extend to envyfree pricing, an important problem in computational economics. We believe that unique coverage has the potential to be a central inapproximable maximization problem in the same way that set cover is for minimization problems.
We mainly focus on the above practical problem in the talk, however if there is any remaining time we also consider the concept of power optimization in faulttolerant topology control algorithms for wireless multihop sensor networks and also define a nice set of theoretical problems on this subject.


Back to Workshop on Flexible Network Design main page
