• Placement of Proxy Servers to Support Server-Based Reliable Multicast. The problem of placing k proxies on a n node network to support server-based 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 re-transmission requests to the sender. Due to high re-transmission requests, the sender could become a potential hot-spot in the network. Also, receivers far away from the sender could experience high delays in receiving the re-transmitted 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 re-transmission 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 Server-Based Reliable Multicast".

• Finding k-connected 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 k-edge-connectivity and k-node-connectivity. Our algorithm for k-node-connectivity 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 non-planarity are monotone properties, while acyclicity and planarity are not. The problems are shown to be NP-hard 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 all-optical 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 well-known channel reservation schemes are Tell-and-Wait (TAW) and Just-Enough-Time (JET). The following introduces a new signaling technique for providing service differentiation based on burst lengths, using intermediate-node initiated signaling in OBS. This technique provides packet-loss probability close to TAW and average end-to-end delay close to JET, thereby capturing the advantages of both TAW and JET.

R. Jothi, V. Vokkarane, B. Raghavachari and J. Jue, "Threshold-Based Differentiated Intermediate-Node Initiated (TDINI) Signaling for Optical Burst-Switched Networks".

• Dynamic Dual-Homing Protection in WDM Mesh Networks. A fault-tolerant scheme, called dual homing, is generally used in IP-based 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 dual-homing 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 Dual-Homing Protection in WDM Mesh Networks".

• The low-power optical network: throughput and fairness (Coauthor: Don Montgomery). Submitted for publication.

• The k-Traveling Repairmen Problem. Given an undirected graph G=(V,E) and a source vertex s in V, the k-traveling 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.5005-approximation 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 1-repairman problem with zero repairtimes. All approximation ratios hold for the multidepot variant of the respective problems as well.
  
  This paper also considers the bounded-latency 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 k-Traveling Repairman Problem".

• The Capacitated Minimum Spanning Tree Problem. Given an undirected graph G=(V,E), non-negative 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 NP-complete, 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 Degree-Bounded Minimum Spanning Trees Problem. Given n points in the Euclidean plane, the degree-d 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 NP-hard for 2 <= d <= 3, while the NP-hardness of the problem is open for d = 4. The problem is polynomial-time solvable when d = 5. In the following paper (submitted for publication), by presenting an improved approximation analysis for Chan's degree-4 MST algorithm, we show that, for any arbitrary collection of points in the Euclidean plane, there always exists a degree-4 spanning tree of weight at most 1.1381 times the weight of an MST.

  R. Jothi and B. Raghavachari, "Degree-Bounded Minimum Spanning Trees".

• The Minimum 2-Edge Connecitivity Problem. Given an undirected, 2-edge-connected graph G=(V,E), the 2-edge-connected spanning subgraph problem (2-ECSS) is to find a minimum cardinality subset of the edges H (subset of E) such that the graph G=(V,H) is 2-edge-connected. The problem is known to be NP-hard. The following  paper describes an approximation algorithm for the 2-ECSS problem with an approximation guarantee of 5/4. The paper is published in the proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003.

  R. Jothi, B. Raghavachari and S. Varadarajan, "A 5/4-Approximation Algorithm for Minimum 2-Edge-Connectivity".

  Current research is focusing on extending the ideas to obtain similar approximation guarantee for 2-vertex-connected spanning subgraph problem (2-VCSS).

• Agent Placement to Support Server-Based 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 well-known 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 NAK-suppression 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 agent-placement 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 NAK-suppression 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 load-balancing among them. In this context, two agent placement problems: the Load-Balanced 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, "Load-Balanced 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 re-compute 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 re-computed trees, for values of m = 1 to m ≈ n/2.

R. Jothi and B.Raghavachari, "Dynamic Capacitated Minimum Spanning Trees".

• Windy Postman Problem. Given a connected, weighted, undirected graph, the Chinese postman problem (CPP) is to find a shortest closed walk of the graph in which each edge is traversed at least once. It is the optimization version of the Euler tour problem, which asks whether there is a closed walk such that each edge is traversed exactly once. Problems such as mail delivery, newspaper delivery, trash pick-up, and snow removal can be modeled by CPP. The problem can be solved in polynomial time if all edges of the graph are undirected, or if all edges are directed. However, if the input graph is mixed, i.e., if it contains both undirected and directed edges, CPP is NP-hard. The Mixed Postman Problem (MPP) is a generalization of CPP, and it enables us to model one-way and two-way streets. Following variation of CPP occurs in several practical scenarios: due to wind (or slope, or some other reason), the cost of traversing an edge in one direction may be cheaper than traversing the edge in the opposite direction. Such a problem is called the Windy Postman Problem (WPP), and it is a generalization of CPP and MPP. Note that the underlying graph is an undirected graph, so the edges can be traversed in any direction, but with different costs. The following paper (submitted for publication) describes an approximation algorithm for the windy postman problem. It is guaranteed to find a solution that is at most 50% more than an optimal solution.

  B. Raghavachari and J. Veerasamy, "A 3/2-approximation algorithm for the windy postman Problem" (compressed Postscript file).

  The above paper builds on an earlier paper by the authors that addresses the mixed postman problem. Research is being done seeking better algorithms for the mixed and windy postman problems that works in planar graphs. The goal is to improve the performance ratio of the algorithms when the input is restricted to planar graphs. It should be noted that many practical instances of the postman problems is already on planar graphs.

• The Directed Minimum-Degree 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 local-search algorithm that finds a low-degree 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 minimum-degree 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 quasi-polynomial time, and in trying to extend the algorithm to the Steiner version of the problem.

• Capacitated Vehicle Routing Problem. Given n identical pegs placed at arbitrary locations, a vehicle with a maximum capacity of k pegs, and n slots (demand points), each requiring a peg, the problem is to find a shortest tour for the vehicle in which all the pegs can be transported to their slots without exceeding the capacity of the vehicle. This problem is known as k-delivery TSP (Traveling salesman problem). The following paper describes approximation algorithms for solving the problem. Several versions of the problem are considered and the approximation ratios are constants, ranging from 4 to 5.5. The paper has been published in SIAM Journal on Computing, 2001.

  M. Charikar, S. Khuller and B. Raghavachari, "Algorithms for capacitated vehicle routing" (compressed Postscript file).

  The version of the problem where there are more pegs than slots, and the algorithm has to select those pegs that will be transported to slots is currently under investigation.

• Dial-A-Ride Problem. Dial-a-Ride 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 demand-responsive transportation systems have been in operation in several metropolitan areas. The Dial-a-Ride 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 single-vehicle Dial-a-Ride systems are not very common, single vehicle Dial-a-Ride algorithms are used as subroutines in large scale multi-vehicle Dial-a-Ride 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 dial-a-ride problem" (compressed Postscript file).

• Traveling Salesman Problem. The bitonic heuristic is a well-known 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 x-axis. 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).