You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format. However, this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the Department of Computer Science of the University of Maryland at College Park under terms that include this permission. All other rights are reserved by the author(s).
Algorithms for Capacitated Vehicle Routing. Moses Charikar. Samir Khuller. Balaji Raghavachari. November 1997.
Given $n$ identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to $n$ target locations (slots) with a vehicle that can carry at most $k$ pegs at a time. This problem is referred to as $k$-delivery TSP, and it is a generalization of the Traveling Salesman Problem. We give a 5-approximation algorithm for the problem of minimizing the total distance traveled by the vehicle. There are two kinds of transportations possible --- one that could drop pegs at intermediate locations and pick them up later in the route for delivery (preemptive) and one that transports pegs to their targets directly (non-preemptive). In the former case, by exploiting the freedom to drop, one may be able to find a shorter delivery route. We construct a non-preemptive tour that is within a factor 5 of the optimal preemptive tour. In addition we show that the ratio of the distances traveled by an optimal non-preemptive tour versus a preemptive tour is bounded by 4. (Also cross-referenced as UMIACS-TR-97-79) University of Maryland Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland,
Sandor P. Fekete. Samir Khuller. Monika Klemmstein. Balaji Raghavachari. Neal Young. A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning. December 1995.
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at most its specified bound is considered. In particular, modifying a given spanning tree $T$ using {\em adoptions} to meet the degree constraints is considered. A novel network-flow based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previously obtained. Equally importantly, it yields the best performance guarantee among the class of algorithms that rely solely on the topology and edge weights of the given tree. The performance guarantee is the following. If the degree constraint $d(v)$ for each $v$ is at least $2$, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times $2 - \min\{\frac{d(v)-2}{\D_T(v)-2} : \D_T(v)>2\},$ where $D_T(v)$ is the initial degree of $v$. Examples are provided in which no lighter tree meeting the degree constraint exists. Linear-time algorithms are provided with the same worst-case performance guarantee. Choosing $T$ to be a minimum spanning tree yields approximation algorithms for the general problem on geometric graphs with distances induced by various $L_p$ norms. Finally, examples of Euclidean graphs are provided in which the ratio of the lengths of an optimal Traveling Salesperson path and a minimum spanning tree can be arbitrarily close to~2. (Also cross-referenced as UMIACS-TR-95-95) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Improved Approximation Algorthmsor Uniform Connectivity Problems. Samir Khuller. Balaji Raghavachari. February 1995.
The problem of finding minimum weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial time approximation algorithms for various weighted and unweighted connectivity problems are given. The following results are presented: 1. For the unweighted k-edge-connectivity problem an approximation algorithm that achieves a performance ratio of 1.85 is described. This is the first polynomial-time algorithm that achieves a constant less than 2, for all k. 2. For the weighted vertex-connectivity problem, a constant factor approximation algorithm is given assuming that the edge-weights satisfy the triangle inequality. This is the first constant factor approximation algorithm for this problem. 3. For the case of biconnectivity, with no assumptions about the weights of the edges, an algorithm that achieves a factor asymptotically approaching 2 is described. This matches the previous best bound for the corresponding edge connectivity problem. (Also cross-referenced as UMIACS-TR-95-21) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Samir Khuller. Balaji Raghavachari. Azriel Rosenfeld. July 28, 1994.
Localization in Graphs. Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a ``graph space''. The robot can locate itself by the presence of distinctively labeled ``landmark'' nodes in the graph space. For a robot navigating in Euclidean space, visual detection of a distinctive landmark provides information about the direction to the landmark, and allows the robot to determine its position by triangulation. On a graph, however, there is neither the concept of direction nor that of visibility. Instead, we shall assume that a robot navigating on a graph can sense the distances to a set of landmarks. Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position on the graph is uniquely determined. This suggests the following problem: given a graph, what are the fewest number of landmarks needed, and where should they be located, so that the distances to the landmarks uniquely determine the robot's position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot's position is called a ``metric basis'', and the minimum number of landmarks is called the ``metric dimension'' of the graph. In this paper we present some results about this problem. Our main {\em new\/} result is that the metric dimension can be approximated in polynomial time within a factor of $O(\log n)$; we also establish some properties of graphs with metric dimension 2. (Also cross-referenced as UMIACS-TR-94-92) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Samir Khuller. Balaji Raghavachari. Neal Young. January 1994.
On Strongly Connected Digraphs with Bounded Cycle Length. The MEG (minimum equivalent graph) problem is "Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes." We consider the complexity of this problem as a function of the maximum cycle length C in the graph. If C =2, the problem is trivial. Recently it was shown that even with the restriction C = 5, the problem is NP-hard. It was conjectured that the problem is solvable in polynomial time if C =3. In this paper we prove the conjecture, showing that the problem is equivalent to maximum bipartite matching. The strong dependence of the complexity on the cycle length is in marked contrast to the relation of complexity and cycle length in undirected graphs. Undirected graphs with bounded cycle length have bounded tree width, allowing polynomial-time algorithms for many problems that are NP-hard in general. A consequence of our result is an improved approximation algorithm for the MEG problem in general graphs. The improved algorithm has a performance guarantee of about 1.61; the best previous algorithm has a performance guarantee of about 1.64. (Also cross-referenced as UMIACS-TR-94-10) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Samir Khuller. Balaji Raghavachari. Neal Young. January 1994.
Low Degree Spanning Trees of Small Weight. Given n points in the plane, the degree-K spanning tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low-weight degree-K spanning trees for K>2. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree three whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of degree four whose weight is at most 1.25 times the weight of a minimum spanning tree. These results solve open problems posed by Papadimitriou and Vazirani. Moreover, if a minimum spanning tree is given as part of the input, the trees can be computed in O(n) time. The results are generalized to points in higher dimensions. It is shown that for any d [greater than or equal to] 3, an arbitrary collection of points in DimD contains a spanning tree of degree three, whose weight is at most 5/3 times the weight of a minimum spanning tree. This is the first paper that achieves factors better than two for these problems. (Also cross-referenced as UMIACS-TR-94-1) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Samir Khuller. Balaji Raghavachari. Neal Young. September 1993.
Maintaining Directed Reachability with Few Edges. The MEG (minimum equivalent graph) problem is the following: ``Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes.'' This problem is NP-hard; this paper gives an approximation algorithm achieving a performance guarantee of about 1.64 in polynomial time. The algorithm achieves a performance guarantee of 1.75 in the time required for transitive closure. The heart of the MEG problem is the minimum SCSS (strongly connected spanning subgraph) problem --- the MEG problem restricted to strongly connected digraphs. For the minimum SCSS problem, the paper gives a practical, nearly linear-time implementation achieving a performance guarantee of 1.75. The algorithm and its analysis are based on the simple idea of contracting long cycles. The analysis applies directly to 2-Exchange, a general ``local improvement'' algorithm, showing that its performance guarantee is 1.75. (Also cross-referenced as UMIACS-TR-93-87) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Samir Khuller. Balaji Raghavachari. Neal Young. March 1993.
Designing Multi-Commodity Flow Trees. The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands.This paper considers the multi-commodity flow network-design problem: given a set of multi-commodity flow demands, find a network subject to certain constraints such that the commodities can be maximally routed. This paper focuses on the case when the network is required to be a tree. The main result is an approximation algorithm for the case when the tree is required to be of constant degree. The algorithm reduces the problem to the minimum-weight balanced-separator problem; the performance guarantee of the algorithm is within a factor of 4 of the performance guarantee of the balanced-separator procedure. If Leighton and Rao's balanced-separator procedure is used, the performance guarantee is O(\log n). This improves the O(\log^2 n) approximation factor obtained by a direct application of the balanced-separator method. (Also cross-referenced as UMIACS-TR-93-20) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Last Generated Fri Aug 11 04:01:01 EDT 2000