
see
the Integrated Logistics Workshop's website

Anant
Balakrishnan
McCombs School of Business,
The University
of Texas at
Austin

Network Design Models for Distribution Systems
Network design models, incorporating tradeoffs between
fixed investments in links or services and operational or
variable costs of routing flows, arise in a variety of strategic,
tactical, and operational planning contexts in distribution
management, ranging from supply chain configuration to detailed
routing and scheduling. This talk will provide an overview
of network design models, their applications, and solution
methods. We present a modeling framework, encompassing variants
and extensions of the network design model, discuss representative
applications in logistics, and outline solution approaches
that have proven effective.
Preliminary presentation: (pdf)



Chandra
Chekuri
Bell Labs,
Lucent
Technologies 
Building EdgeFailure Resilient Networks
We consider the design of resilient networks that are fault
tolerant against link failures. Resilience against link
failures can be built into the network by providing backup
paths, which are used when an edge failure occurs on a primary
path. We consider several network design problems in this
context: the goal is to provision primary and backup bandwidth
while minimizing cost. Our models are motivated by current
high speed optical networks and we provide approximation
algorithms for the problems.
Joint work with Anupam
Gupta, Amit Kumar, Seffi Naor, and
Danny Raz.
Preliminary presentation: (pdf)
(ppt)



Ashish Goel
Stanford 
Simultaneous Optimization with Concave Costs or Concave
Profits
In simultaneous optimization, we need to simultaneously
approximate a whole family of objective functions. In this
talk, we will consider two problems:
a) Suppose we want to construct a tree for sending information
from a single source to k sinks. Further, suppose that
the cost of sending x units of information over a link is
proportional to f(x), where f is concave, f(0) = 0, and
f is nondecreasing. This problem is known as single source
buyatbulk network design. We will present a simple randomized
algorithm that guarantees an O(log k) approximation to the
cheapest tree for all such functions f, simultaneously.
b) Suppose we want to assign bandwidth to N network connections,
and the utility of the system is some symmetric concave
function, U, of assigned bandwidths. We present a simple
distributed algorithm, based on the primaldual approach,
that simultaneously provides a logarithmic approximation
for all U.
Part (a) represents joint work with
Deborah Estrin and
(b) represents joint work with Sungwoo
Cho.



Marc
Goetschalckx
Georgia Institute of Technology

Modeling of Strategic Supply Chain Design Problems Under
Uncertainty
Preliminary presentation: (pdf)



Srinivas
Kashyap 
Approximation Algorithms for Data Placement on Parallel
Disks
We study a problem that arises in the context of data
placement in multimedia storage systems. We are given a
collection of M multimedia objects (data items) that need
to be assigned to a storage system consisting of N disks.
We are also given the demand for each data item. Each data
item has a size s_i. Disks are typically characterized by
two parameters, its storage capacity k, and a load capacity
L which indicates the maximum number of users that it can
serve. The goal is to find a placement of data items on
the disks and an assignment of users to disks so as to maximize
the total number of users served, subject to the capacity
constraints of the storage system.
The talk presents the first successful attempt at removing
the assumption that all data items have unit size. We develop
a polynomial time approximation scheme (PTAS) for all instances
where s_i in {1,...,D} for some constant D.
The talk also presents an algorithm for which we can prove
tight bounds on the number of users that can be served,
regardless of the input distribution, when s_i in {1,2}.
In other words there are instances where no placement of
data items and assignment of load can guarantee a better
packing.
This is a joint work with Samir
Khuller.
Preliminary presentation: (pdf)



Samir
Khuller
University of Maryland 
Algorithms for Data Migration with Cloning
Our work is motivated by the problem of managing data on
storage devices, typically a set of disks. Such high demand
storage servers are used as web servers, or multimedia servers
for handling high demand for data. As the system is running,
it needs to dynamically respond to changes in demand for
different data items. In this work we study the data
migration problem, which arises when we need to quickly
change one storage configuration into another. We show that
this problem is NPhard. In addition, we develop polynomial
time approximation algorithms for this problem and prove
a worst case bound of 9.5 on the approximation factor achieved
by our algorithm. We also compare the algorithm to several
heuristics for this problem.
Joint work with
Yoo Ah Kim and Justin
Wan.



Amit
Kumar
Bell Laboratories 
A ConstantFactor Approximation
Algorithm for the Multicommodity RentorBuy Problem
In this talk, I shall present the first constantfactor
approximation algorithm for network design with multiple
commodities and economies of scale. We consider the rentorbuy
problem, a type of multicommodity buyatbulk network design
in which there are two ways to install capacity on any given
edge. Capacity can be rented, with cost incurred on
a perunit of capacity basis, or bought, which allows
unlimited use after payment of a large fixed cost.
Given a graph and a set of sourcesink pairs, we seek a
minimumcost way of installing sufficient capacity on edges
so that a prescribed amount of flow can be sent simultaneously
from each source to the corresponding sink.
Recent work on buyatbulk network design has concentrated
on the special case where all sinks are identical; existing
constantfactor approximation algorithms for this special
case make crucial use of the assumption that all commodities
ship flow to the same sink vertex and do not obviously extend
to the multicommodity rentorbuy problem. Prior to
our work, the best heuristics for the multicommodity rentorbuy
problem achieved only logarithmic performance guarantees
and relied on the machinery of relaxed metrical task systems
or metric embeddings. By contrast, we solve the network
design problem directly via a novel primaldual algorithm.
This is joint work with Anupam
Gupta and Tim
Roughgarden.
Preliminary presentation: (pdf)
(ppt)



Bruce Maggs
Carnegie Mellon 
Designing Overlay Multicast Networks for Streaming



Amitabh
Sinha
Carnegie Mellon
GSIA 
Locating Nursing Stations: Covering Graphs Using Trees and
Stars
A tree cover of a graph $G$ is defined as a collection
of trees such that their union includes all the vertices
of $G$. The weight of a tree cover is the weight of the
maximum weight tree in the tree cover. Given a positive
integer $k$, the $k$tree cover problem is to compute a
minimum cost tree cover which has no more than $k$ trees.
Star covers are defined analogously. Additionally, we may
also be provided with a set of $k$ vertices which are to
serve as roots of the trees or stars. In this paper, we
provide constant factor approximation algorithms for finding
tree and star covers of graphs, in the rooted and unrooted
versions.
Joint work with Guy
Even, Naveen Garg, Jochen Konemann and
R. Ravi.
Preliminary presentation: (pdf)



Tom Wexler
Cornell 
Nash Equilibria in a New Connection Game
We introduce a new game in which players seek to connect
pairs of terminals in a graph. Players are allowed to share
edges that are fully paid for, and each player seeks to
pay as little as possible while still connecting his terminals.
The centralized version of this game is simply the generalized
Steiner tree problem. However, in a game where all agents
act selfishly, there may be no stable solution, i.e. a Nash
equilibrium may not exist. We explore some situations where
equilibria do exist, and develop bicriteria approximations
for studying solutions which are nearly stable.
This is part of joint work with Elliot
Anshelevich, Anirban Dasgupta, and
Eva Tardos to appear
in STOC 03.
Preliminary presentation: (pdf)
(ppt)



Prakash
Mirchandani
University of Pittsburgh 
Designing Survivable Networks:
A FlowBased Approach Logistics and communication
networks designed from a pure costefficiency perspective
tend to be sparse and have little spare capacity. Consequently,
edge failures in such networks can lead to the disruption
of service between many pairs of network locations, possibly
resulting in severe economic losses. In this paper, we consider
the problem of designing costeffective, but failuretolerant
networks. Given a network with required connectivity levels,
specified as the number of edgedisjoint paths needed between
each node pair, we seek the minimum cost topological design
that meets these connectivity requirements. Even the simplest
special cases of this problem are computationally difficult.
We propose a new flowbased approach for modeling this problem,
and develop valid inequalities that further strengthen this
formulation. Our preliminary computational results for problem
instances having up to 400 integer variables show that our
procedure generates solutions that are on average within
1 % of optimality in a reasonable amount of computational
time.
This work is joint with Anant
Balakrishnan.
Preliminary presentation: (pdf)



Eva Tardos
Cornell

Network Design with Selfish
Agents In this talk we will consider several
network design games with selfish agents.
Maybe the simplest network design games are facility location
and spanning treegames when goal of each player is to connect
a terminal to a facility or to a common source in the graph.
Facilities, and potential edges in the network have costs
and each agent's goal is to pay as little as possible, while
having his terminals connected. We will consider these and
related games both from the perspective of cost sharing,
and that of the quality of Nash equalibria.
The result presented are joint work with
Elliot Anshelevich, Anirban Dasgupta,
Martin Pal, and Tom
Wexler.



Martin
Pal
Cornell
University 
Multicommodity Rent or Buy: Approximation
via CostSharing
In the Steiner forest problem we are given a graph and
a set of pairs of demands that need to communicate. The
goal is to buy a set of edges so that each pair is connected
by a path. In the multicommodity rent or buy problem we
can for each edge choose either to buy it at a high fixed
cost, or rent it, paying rental cost for each path using
the edge.
In this talk I will present a cost sharing algorithm for
the Steiner forest problem and show how this algorithm together
with a simple randomized analysis yields a constant factor
approximation algorithm fo the multicommodity rent or buy
problem. The cost shares are generated by a natural dual
growing process, while the Steiner forest is constructed
by a procedure that can be viewed as an "inflated version"
of the Steiner forest algorithm by Agarwal, Klein and Ravi,
and Goemans and Williamson.
Joint work with Anupam
Gupta, Amit Kumar, and Tim
Roughgarden.
Preliminary presentation:
(ppt)
(pdf)



Andrew
Schaefer
University of Pittsburgh 
The Optimal Design and Operation
of Remnant Inventory Systems
This presentation discusses the integrated design and operation
of an inventory control and distribution system for remnant
inventory. Such inventory is encountered in the supply
chains of various onedimensional products such as rolls
of steel, aluminum, paper, fabric, etc. where the product
is produced in "standard" sizes but demands occur
in "nonstandard" sizes. This ongoing
research (a) combines elements of several classical O.R.
problem areas including the cutting stock problem, inventory
management, facility location, and distribution, and (b)
proposes the use of several different O.R. techniques such
as Benders’ decomposition, stochastic programming,
and remnant inventory control. Based on earlier work by
Adelman and Nemhauser, a combined location/distribution
network model is described for the problem where locations
for both inventory distribution points and demand are geographically
dispersed. We also assume that scrap can be recycled,
and discuss extensions such as stochastic demand and raw
material sizing.



see
the Integrated Logistics Workshop's website
