 Placement of Proxy Servers to Support ServerBased Reliable Multicast.
The problem of placing k proxies on a n node network to support
serverbased
reliable multicast is considered. Typically, in a multicast connection, the sender
transmits information to all the receivers in the multicast group. Failures in
transmission causes receivers to send retransmission requests to the sender. Due
to high retransmission requests, the sender could become a potential hotspot in
the
network. Also, receivers far away from the sender could experience high delays in
receiving the retransmitted information. To prevent these and other issues, the
notion
of placing proxy (or repair) servers across the network was introduced, so that
receivers could send their retransmission requests to the nearby proxy servers
than
to the source. The following paper (to appear in ICN 2004) considers the static
placement
of proxies on a network in which multicast requests (trees) are generated
dynamically.
The placement of proxies should be such that the proxies are utilized efficiently
by the
dynamically generated multicast trees.
R. Jothi and B. Raghavachari,
"Placement of Proxy Servers to Support ServerBased Reliable
Multicast".

 Finding kconnected subgraphs with minimum average weight
(Coauthor: Prabhakar Gubbala).
Given a graph G=(V,E) that satisfies a specified property P, and
a cost function c on its edges, we consider the problem of finding
a subgraph of G that also satisfies P with minimum average weight.
In this paper, we consider the properties of kedgeconnectivity
and knodeconnectivity. Our algorithm for knodeconnectivity
also extends to any monotone property on graphs. P is a monotone property
if G continues to satisfy P after the addition of arbitrary additional
edges to G (connecting existing vertices). Connectivity and
nonplanarity are monotone properties, while acyclicity and planarity are not.
The problems are shown to be NPhard and approximation algorithms are provided.
(Submitted for publication.)

 Signaling for Optical Burst Switched Networks. Recent increase
in the bursty broadband traffic on the internet has paved way for the fast
evolving Optical Burst Switching (OBS). In OBS, bursts of data, composed
of several packets, are switched through the bufferless alloptical WDM
networks~\cite{Q99}. Packets arriving at the edge nodes are first
accumulated into bursts, which are then transmitted through the network
based on one or more of several channel reservation schemes. Two
wellknown channel reservation schemes are TellandWait (TAW) and
JustEnoughTime (JET). The following introduces a new signaling technique
for providing service differentiation based on burst lengths, using
intermediatenode initiated signaling in OBS. This technique provides
packetloss probability close to TAW and average endtoend delay close to
JET, thereby capturing the advantages of both TAW and JET.
R. Jothi, V. Vokkarane, B. Raghavachari and J. Jue,
"ThresholdBased Differentiated IntermediateNode Initiated (TDINI)
Signaling for Optical BurstSwitched Networks".

 Dynamic DualHoming Protection in WDM Mesh Networks.
A faulttolerant scheme, called dual
homing, is generally used in IPbased access networks to increase the
availability of the network. In dual homing, a host is connected to two
different access routers; therefore, it is unlikely that the host will be
denied access to the network as the result of an access line break, a
defective power supply in the access router, or congestion of the access
router. However, dual homing itself cannot provide survivability due to
possible failures in a WDM core network. To provide survivability in the
core network, protection and restoration techniques must be
used. The dual homing architecture introduces new issues for protection
and restoration design, especially when providing survivability against
two independent failures, one in the access network and another in the
core network. The following paper (submitted for publication) studies the
protection design in the core network given the dualhoming infrastructure
in WDM mesh networks. Several solutions are proposed, and the performance
of the different solutions are compared. We also prove that one of the
proposed algorithms gives a solution that, in the worst case, is at most
4/3 times the cost of an optimal solution.
V. Vokkarane, J. Wang, R. Jothi, X. Qi, B. Raghavachari and J. Jue,
"Dynamic DualHoming Protection in WDM Mesh Networks".

 The lowpower optical network: throughput and fairness
(Coauthor: Don Montgomery).
Submitted for publication.

 The kTraveling Repairmen Problem. Given an undirected graph
G=(V,E) and a source vertex s in V, the ktraveling
repairman (KTR) problem, also known as the minimum latency problem, asks
for k tours, each starting at s and covering all the
vertices (customers), such that the sum of the latencies experienced by
the customers is minimum. Latency of a customer p is defined
to be the distance traveled before visiting p for the first time.
Previous literature on the KTR problem has considered the version of the
problem in which the repairtime of a customer is assumed to be zero for
latency calculations. In the following paper (submitted for publication),
a generalization of the problem in which each customer is associated with
some repairtime. In this paper, a (3β
+1)approximation algorithm for this problem is presented, where
β is the best achievable approximation
ratio for the KTR problem with zero repairtimes. For the case when the
repairtimes of all the customers are the same, a 7.5005approximation
algorithm is presented. For the case, when k=1, a ratio of 3γ+1
is obtained, where γ is the best
achievable approximation ratio for the 1repairman problem with zero
repairtimes. All approximation ratios hold for the multidepot variant of
the respective problems as well.
This paper also considers the boundedlatency problem, a complementary
version of the KTR problem in which a latency bound L is given as
input. The objective of this problem is to find the minimum number of
repairmen required to service all the customers such that the latency of
no customer is more than L. For this problem, a bicriteria
approximation algorithm is presented, which finds a solution with at most
2ρ times the number of repairmen
required by an optimal solution, with the latency of no customer exceeding
(1+ρ)L,
ρ > 0.
R. Jothi and B. Raghavachari, "Minimum Latency Tours and the
kTraveling Repairman Problem".

 The Capacitated Minimum Spanning Tree Problem. Given an
undirected graph G=(V,E), nonnegative weights on its edges
and vertices, vertex r in V, and a positive number k,
the capacitated minimum spanning tree (CMST) problem asks for a minimum
spanning tree rooted at r such that the sum of the vertex weights
of every subtree (cluster weight), hanging off r, is at most k.
The problem is NPcomplete, even if all vertices are of unit weight and
k=3. In the following paper (submitted for publication), we present an
improved approximation algorithm for the CMST problem.
R. Jothi and B. Raghavachari, "Toplogical Design of Centralized
Communication Networks".
For graphs whose edges obey geometric properties, we present improved
approximation algorithms with ratios improving 15 year old previous
results. This along with other results for related network design problems
are presented in the following paper (submitted for publication).
R. Jothi and B. Raghavachari, "Approximation Algorithms for the
Capacitated Minimum Spanning Tree Problem and its Variants in Network
Design".
The following paper contains a new heuristic we proposed for the CMST
problem, which outperforms or matches the results of the, 37 year old,
current best heuristic due to Esau and Williams. This paper has been
accepted for publication in the proceedings of the 15th IASTED
International Conference on Parallel and Distributed Computing and Systems
(PDCS), 2003.
R. Jothi and B. Raghavachari, "Design of Local Access Networks".

 The DegreeBounded Minimum Spanning
Trees Problem. Given n points in the Euclidean plane, the degreed
minimum spanning tree problem asks for a spanning tree of minimum weight
in which the degree of each vertex is at most d. This problem is
NPhard for 2 <= d <= 3, while the NPhardness of the problem is open
for d = 4. The problem is polynomialtime solvable when d = 5.
In the following paper (submitted for publication), by presenting an
improved approximation analysis for Chan's degree4 MST algorithm, we show
that, for any arbitrary collection of points in the Euclidean plane, there
always exists a degree4 spanning tree of weight at most 1.1381 times the
weight of an MST.
R. Jothi and B. Raghavachari, "DegreeBounded Minimum Spanning
Trees".


 Agent Placement to Support ServerBased Reliable Multicast.
In reliable multicast, receivers use negative acknowledgments (NAKs) to
inform the sender about their packet loss. The growth in the number of NAK
messages received by the sender results in the wellknown feedback (or NAK)
implosion problem. Therefore, one important issue for reliable multicast
protocols is to utilize an effective mechanism to collect NAK messages from
the receivers. One way to avoid feedback implosion at the sender site is to
place NAKsuppression agents on the internal nodes (routers) of the network.
These agents will forward a single copy of the incoming NAK messages toward
the sender site and will suppress additional redundant copies coming from
the receivers.
The following papers (submitted for publication) consider the
agentplacement problem for reliable multicast. The input is a multicast
tree rooted at the multicast sender node, with the leaves of the tree
being the multicast group members (receivers). The internal nodes of the
tree (routers) are assumed to have NAKsuppression capabilities. The
objective is to select a subset of internal nodes for NAK suppression task
for a given reliable multicast application. The main selection criteria is
to choose a minimum number of such nodes for the task and have a notion of
loadbalancing among them. In this context, two agent placement problems:
the LoadBalanced Agent Placement Problem (LBAPP) and the
Budgeted Agent Placement Problem (BAPP) are studied. Efficient
algorithms for optimal placement of agents are presented.
O. Daescu, R. Jothi, S. Peri, B. Raghavachari and K. Sarac,
"LoadBalanced Agent Placement for Reliable Multicast".
O. Daescu, R. Jothi, B. Raghavachari and K. Sarac, "Optimal
Placement of NAK Suppressing Agents for Reliable Multicast: A Partial
Deployment Case".

 Dynamic Capacitated Minimum Spanning Tree Problem. Given a
capacitated minimum spanning tree (CMST) T spanning n nodes
(with capacity constraint k) and rooted at node r.
Requests from new nodes (not in T) for joining T arrive
dynamically, one at a time. Under this setting, the new node should be added
to T without having to recompute the whole CMST (a simple and
efficient heuristic to compute a CMST takes at least O(n^2 log n)
time). The following paper (to appear in ICN 2004) contains three
proposed heuristics for this problem, each of which takes O(n) time.
If m were the total number of new requests, experimental results show
that the best heuristic, NASPC, computes trees of cost at most 1.5 times the
cost of recomputed trees, for values of m = 1 to m
≈ n/2.
R. Jothi and B.Raghavachari, "Dynamic Capacitated Minimum Spanning
Trees".



The Directed MinimumDegree Spanning Tree Problem. Given a
directed graph G = (V,E) with n vertices and a root
vertex r, consider the problem of constructing a spanning tree
rooted at r (also known as a branching) whose maximal degree
is the smallest among all branchings of G rooted at r. The
following paper (submitted for publication) describes a localsearch
algorithm that finds a lowdegree branching. It is shown that it
finds a branching whose degree is within an additive log n
from the degree of an optimal branching. The paper has been published in the
proceedings of the 21st Conference on Foundations of Software Technology and
Theoretical Computer Science (FSTTCS), 2001.
R. Krishnan and B. Raghavachari,
"The directed minimumdegree spanning tree problem"
(compressed Postscript file).
Current research is focusing on improving the algorithm so that its
running time is polynomial, instead of the current quasipolynomial
time, and in trying to extend the algorithm to the Steiner version
of the problem.



DialARide Problem. DialaRide systems involve dispatching
a vehicle to satisfy demands from a set of customers who call a
vehicle operating agency requesting that an item be picked up from a
specific location and delivered to a specific destination. Such
demandresponsive transportation systems have been in operation in
several metropolitan areas. The DialaRide problem arises in
several practical applications such as the transportation of elderly
and disabled persons, shared taxi services and courier services.
The problem is modeled as follows. We are given n customers,
each at some initial position, and each person has his/her target
destination. A taxi company with a vehicle of capacity k has
the task of transporting each customer to their destination.
Different customers may share the ride during their journey, but at
any given time, the taxi may carry at most k passengers. The
goal is to minimize the total distance traveled by the taxi in
transporting all the passengers. Although singlevehicle
DialaRide systems are not very common, single vehicle DialaRide
algorithms are used as subroutines in large scale multivehicle
DialaRide environments. The following paper, which provides an approximation algorithm for the
problem, has been published in the proceedings of the 39th annual Symposium on
Foundations of Computer Science (FOCS), 1998.
M. Charikar and B. Raghavachari,
"The finite capacity dialaride problem" (compressed
Postscript file).


Traveling Salesman Problem. The bitonic heuristic is a
wellknown algorithm for solving the traveling salesman problem when
the input points are defined on the plane. The algorithm finds a
solution in which the points are covered in two sweeps of the plane
along the xaxis. The algorithm is very fast, but the length of the
tour that it generates could be significantly more than the optimal
solution. The performance of variations of this scheme on random
instances of the problem is studied experimentally. The algorithm
is also extended to higher dimensions.
N. R. Nagubhai and B. Raghavachari, "Experimental studies of
the bitonic heuristic to the traveling salesman problem (manuscript
under preparation).
