### Browsing by Author "Khuller, Samir"

Now showing 1 - 20 of 29

###### Results Per Page

###### Sort Options

Item Algorithms for Capacitated Vehicle Routing(1998-10-15) Charikar, Moses; Khuller, Samir; Raghavachari, BalajiGiven $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)Item Approximation Algorithms for Connected Dominating Sets(1998-10-15) Guha, Sudipto; Khuller, SamirThe dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to either be in the dominating set, or adjacent to some node in the dominating set. We focus on the question of finding a {\em connected dominating set} of minimum size, where the graph induced by vertices in the dominating set is required to be {\em connected} as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of $O(H(\Delta))$ are presented, where $\Delta$ is the maximum degree, and $H$ is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited, or has at least one of its neighbors visited. We study a generalization of the problem when the vertices have weights, and give an algorithm which achieves a performance ratio of $3 \ln n$. We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide an $O(H(\Delta))$ approximation factor. To prove the bound we also develop an optimal approximation algorithm for the unit node weighted Steiner tree problem. (Also cross-referenced as UMIACS-TR-96-47)Item Approximation Algorithms for Finding Highly Connected Subgraphs(1998-10-15) Khuller, Samir(Also cross-referenced as UMIACS-TR-95-4)Item Approximation Algorithms for Partial Covering Problems(2001-05-10) Gandhi, Rajiv; Khuller, Samir; Srinivasan, AravindWe study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-vertex cover) in polynomial time. In addition to its simplicity, this algorithm has the advantage of being parallelizable. For instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better than 2-approximation algorithms for k-vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-vertex cover on planar graphs, and for covering points in R^d by disks. (Cross-referenced as UMIACS-TR-2001-23)Item The Capacitated K-Center Problem(1998-10-15) Khuller, Samir; Sussmann, Yoram J.The capacitated $K$-center problem is a fundamental facility location problem, where we are asked to locate $K$ facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. Moreover, each facility may be assigned at most $L$ vertices. This problem is known to be NP-hard. We give polynomial time approximation algorithms for two different versions of this problem that achieve approximation factors of 5 and 6. We also study some generalizations of this problem. (Also cross-referenced as UMIACS-TR-96-39)Item A Clustering Scheme for Hierarchical Routing in Wireless Networks(2000-03-01) Banerjee, Suman; Khuller, SamirIn this paper we present a clustering scheme to create hierarchies for wireless networks. A cluster is defined as a subset of vertices, whose induced graph is connected. In addition, a cluster is required to obey certain constraints that are useful for hierarchical routing. While all these constraints cannot be met simultaneously for general graphs, we show how for wireless network topologies, such a clustering can be obtained. We also present simulation results from a distributed implementation of this scheme to demonstrate its convergence and stability properties.Item The Complexity of Finding Most Vital Arcs and Nodes(1998-10-15) Bar-Noy, Amotz; Khuller, Samir; Schieber, BaruchLet $G(V,E)$ be a graph (either directed or undirected) with a non-negative length $\ell(e)$ associated with each arc $e$ in $E$. For two specified nodes $s$ and $t$ in $V$, the $k$ most vital arcs (or nodes) are those $k$ arcs (nodes) whose removal maximizes the increase in the length of the shortest path from $s$ to $t$. We prove that finding the $k$ most vital arcs (or nodes) is NP-hard, even when all arcs have unit length. We also correct some errors in an earlier paper by Malik, Mittal and Gupta [ORL 8:223-227, 1989]. (Also cross-referenced as UMIACS-TR-95-96)Item Data Migration on Parallel Disks(2003-12-18) Golubchik, Leana; Khuller, Samir; Kim, Yoo-Ah; Shargorodskaya, Svetlana; Wan, Yung-Chun (Justin)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. There are known algorithms for mapping demand to a layout. When the demand changes, a new layout is computed. In this work we study the data migration problem, which arises when we need to quickly change one layout to another. This problem has been studied earlier when for each disk the new layout has been prescribed. However, lack of such information leads to an interesting problem that we call the correspondence problem, whose solution has a significant impact on the solution for the data migration problem. We examine algorithms for the data migration problem in more detail and identify variations of the basic algorithm that seem to improve performance in practice, even though some of the variations have poor worst case behavior. UMIACS-TR-2003-115Item Design and Analysis of Algorithms: Course Notes(1998-10-15) Khuller, SamirThese are my lecture notes from CMSC 651: Design and Analysis of Algorithms}, a one semester course that I taught at University of Maryland in the Spring of 1993. The course covers core material in algorithm design, and also helps students prepare for research in the field of algorithms. The reader will find an unusual emphasis on graph theoretic algorithms, and for that I am to blame. The choice of topics was mine, and is biased by my personal taste. The material for the first few weeks was taken primarily from the (now not so new) textbook on Algorithms by Cormen, Leiserson and Rivest. A few papers were also covered, that I personally feel give some very important and useful techniques that should be in the toolbox of every algorithms researcher. (Also cross-referenced as UMIACS-TR-93-72)Item Designing Multi-Commodity Flow Trees(1998-10-15) Khuller, Samir; Raghavachari, Balaji; Young, NealThe 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)Item Efficient Minimum Cost Matching and Transportation Using Quadrangle Inequality(1998-10-15) Aggarwal, Alok; Bar-Noy, Amotz; Khuller, Samir; Kravets, Dina; Schieber, BaruchWe present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G=(\Red\cup \Blue, \Red\times \Blue), where |\Red|=n, |\Blue|=m, n\le m, and the cost function obeys the quadrangle inequality. First, we assume that all the \red\ points and all the \blue\ points lie on a curve that is homeomorphic to either a line or a circle and the cost function is given by the Euclidean distance along the curve. We present a linear time algorithm for the matching problem that is simpler than the algorithm of \cite{kl75}. We generalize our method to solve the corresponding transportation problem in O((m+n) \log (m+n)) time, improving on the best previously known algorithm of \cite{kl75}. Next, we present an O(n\log m)-time algorithm for minimum cost matching when the cost array is a bitonic Monge array. An example of this is when the \red\ points lie on one straight line and the \blue\ points lie on another straight line Finally, we provide a weakly polynomial algorithm for the transportation problem in which the associated cost array is a bitonic Monge array. Our algorithm for this problem runs in O(m \log(\sum_{j=1}^m \sj_j)) time, where \di_i is the demand at the ith sink, \sj_j is the supply available at the jth source, and \sum_{i=1}^n \di_i \le \sum_{j=1}^m \sj_j. (Also cross-referenced as UMIACS-TR-93-140)Item Facility Location with Dynamic Distance Functions(1998-10-15) ; Bhatia, Randeep; Guha, Sudipto; Khuller, Samir; Sussmann, Yoram J.Facility location problems have always been studied with the assumption that the edge lengths in the network are {\em static} and do not change over time. The underlying network could be used to model a city street network for emergency facility location/hospitals, or an electronic network for locating information centers. In any case, it is clear that due to traffic congestion the traversal time on links {\em changes} with time. Very often, we have some estimates as to how the edge lengths change over time, and our objective is to choose a set of locations (vertices) as centers, such that at {\em every} time instant each vertex has a center close to it (clearly, the center close to a vertex may change over time). We also provide approximation algorithms as well as hardness results for the $K$-center problem under this model. This is the first comprehensive study regarding approximation algorithms for facility location for good time-invariant solutions. (Also cross-references as UMIACS-TR-97-70)Item Fault Tolerant K-Center Problems(1998-10-15) Khuller, Samir; Pless, Robert; Sussmann, Yoram J.The basic $K$-center problem is a fundamental facility location problem, where we are asked to locate $K$ facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. This problem is known to be NP-hard, and several optimal approximation algorithms that achieve a factor of $2$ have been developed for it. We focus our attention on a generalization of this problem, where each vertex is required to have a set of $\alpha$ ($\alpha \le K$) centers close to it. In particular, we study two different versions of this problem. In the first version, each vertex is required to have at least $\alpha$ centers close to it. In the second version, each vertex that {\em does not have a center placed on it} is required to have at least $\alpha$ centers close to it. For both these versions we are able to provide polynomial time approximation algorithms that achieve constant approximation factors for {\em any} $\alpha$. For the first version we give an algorithm that achieves an approximation factor of $3$ for any $\alpha$, and achieves an approximation factor of $2$ for $\alpha < 4$. For the second version, we provide algorithms with approximation factors of $2$ for any $\alpha$. The best possible approximation factor for even the basic $K$-center problem is 2. In addition, we give a polynomial time approximation algorithm for a generalization of the $K$-supplier problem where a subset of at most $K$ supplier nodes must be selected as centers so that every demand node has at least $\alpha$ centers close to it. We also provide polynomial time approximation algorithms for all the above problems for generalizations when cost and weight functions are defined on the set of vertices. (Also cross-referenced as UMIACS-TR-96-40)Item The Full Degree Spanning Tree Problem(1998-10-15) Bhatia, Randeep; Khuller, Samir; Pless, Robert; Sussmann, YoramThe full degree spanning tree problem is defined as follows: given a connected graph $G=(V,E)$ find a spanning tree $T$ so as to maximize the number of vertices whose degree in $T$ is the same as in $G$ (these are called vertices of ``full'' degree). We show that this problem is NP-hard. We also present almost {\em optimal} approximation algorithms for it assuming $coR \neq NP$. For the case of general graphs our approximation factor is $\Theta(\sqrt{n})$. Using H{\aa}stad's result on the hardness of approximating clique, we can show that if there is a polynomial time approximation algorithm for our problem with a factor of $O(n^{\frac{1}{2}-\epsilon})$ then $coR=NP$. For the case of planar graphs, we present a polynomial time approximation scheme. Additionally, we present some experimental results comparing our algorithm to the previous heuristic used for this problem. (Also cross-referenced as UMIACS 98-47)Item An Improved Approximation Algorithm For Vertex Cover with Hard Capacities(2003-04-04) Gandhi, Rajiv; Halperin, Eran; Khuller, Samir; Kortsarz, Guy; Srinivasan, AravindIn this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph $G=(V,E)$, the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex cover problem. Previously, $2$-approximation algorithms were developed with the assumption that multiple copies of a vertex may be chosen in the cover. If we are allowed to pick at most a given number of copies of each vertex, then the problem is significantly harder to solve. Chuzhoy and Naor (\textit{Proc.\ IEEE Symposium on Foundations of Computer Science, 481--489, 2002}) have recently shown that the weighted version of this problem is at least as hard as set cover; they have also developed a $3$-approximation algorithm for the unweighted version. We give a $2$-approximation algorithm for the unweighted version, improving the Chuzhoy-Naor bound of $3$ and matching (up to lower-order terms) the best approximation ratio known for the vertex cover problem. UMIACS-TR-2003-30Item Improved Approximation Algorthmsor Uniform Connectivity Problems(1998-10-15) Khuller, Samir; Raghavachari, BalajiThe 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)Item Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets(1998-10-15) Guha, Sudipto; Khuller, SamirA greedy approximation algorithm based on ``spider decompositions'' was developed by Klein and Ravi for node weighted Steiner trees. This algorithm provides a worst case approximation ratio of $2 \ln k$, where $k$ is the number of terminals. However, the best known lower bound on the approximation ratio is $\ln k$, assuming that $NP \not\subseteq DTIME[n^{O(\log \log n)}]$, by a reduction from set cover. We show that for the unweighted case we can obtain an approximation factor of $\ln k$. For the weighted case we develop a new decomposition theorem, and generalize the notion of ``spiders'' to ``branch-spiders'', that are used to design a new algorithm with a worst case approximation factor of $1.5 \ln k$. This algorithm, although polynomial, is not very practical due to its high running time; since we need to repeatedly find many minimum weight matchings in each iteration. We are able to generalize the method to yield an approximation factor approaching $1.35 \ln k$. We also develop a simple greedy algorithm that is practical and has a worst case approximation factor of $1.6103 \ln k$. The techniques developed for the second algorithm imply a method of approximating node weighted network design problems defined by 0-1 proper functions. These new ideas also lead to improved approximation guarantees for the problem of finding a minimum node weighted connected dominating set. The previous best approximation guarantee for this problem was $3 \ln n$. By a direct application of the methods developed in this paper we are able to develop an algorithm with an approximation factor approaching $1.35 \ln n$. (Also cross-referenced as UMIACS-TR-97-80)Item The Loading Time Scheduling Problem(1998-10-15) Bhatia, Randeep; Khuller, Samir; Naor, Joseph (Seffi)In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the machines. Each machine has a loading time that is incurred only for the first task that is scheduled on the machine in a particular run. This basic scheduling problem arises in the context of machining on numerically controlled machines, query optimization in databases, and in other artificial intelligence applications. We give the first non-trivial approximation algorithm for this problem. We also prove non-trivial lower bounds on best possible approximation ratios for these problems. These improve on the non-approximability results that are implied by the non-approximability results for the shortests common supersequence problem. We use the same algorithmic technique to obtain approximation algorithms for a problem arising in the context of code generation for parallel machines, and for the weighted shortest common supersequence problem.Item Localization in Graphs(1998-10-15) Khuller, Samir; Raghavachari, Balaji; Rosenfeld, AzrielNavigation 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)Item Localizing an object with finger probes(1998-10-15) Freimer, Robert; Khuller, Samir; Mitchell, Joe; Piatko, Christine; Romanik, Kathleen; Souvaine, DianeWe consider the problem of identifying one of a set of polygonal models in the plane using point probes and finger probes. In particular, we give strategies for using a minimum number of finger probes to determine a finite number of possible locations of an unknown interior point in one of the models. A finger probe takes as input an interior point $p$ of a polygon $P$ and a direction $\theta$, and it outputs the first point of intersection of a ray emanating from $p$ in direction $\theta$ with the boundary of $P$. We show that without a priori knowledge of what the models look like, no finite number of finger probes will suffice. When the models are given in advance, we give both batch and dynamic probing strategies for solving the problem. We consider both the case where the models are aligned rectilinear polygons and the case where the models are simple polygons. (Also cross-referenced as UMIACS-TR-94-114)