Browsing by Author "Gandhi, Rajiv"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Approximation Algorithms for Partial Covering Problems
    (2001-05-10) Gandhi, Rajiv; Khuller, Samir; Srinivasan, Aravind
    We 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)
  • Thumbnail Image
    Item
    Domain Name Based Visualization of Web Histories in a Zoomable User Interface
    (2000) Gandhi, Rajiv; Kumar, Girish; Bederson, Benjamin B.; Shneiderman, Ben; ISR
    Users of hypertext systems like the World Wide Web (WWW) often find themselves following hypertext links deeper and deeper, only to become "lost" and unable to find their way back to the previouslyvisited pages. We have implemented a web browser companion called Domain Tree Browser (DTB) that builds a tree structured visual navigation history while browsing the web. The Domain Tree Browser organizes the URLs visited based on the domain name of each URL and shows thumbnails of each page in a zoomable window. A usability test was conducted with four subjects.
  • Thumbnail Image
    Item
    Fast Distributed Well Connected Dominating Sets for Ad Hoc Networks
    (2004-02-25) Parthasarathy, Srinivasan; Gandhi, Rajiv
    We present the first distributed algorithms for computing connected dominating sets (CDS) for ad hoc networks that break the linear-time barrier. We present two algorithms which require O(Delta log^2(n)) and O(log^2(n)) running time respectively, where Delta is the maximum node degree and 'n' is the size of the network. This is a substantial improvement over existing implementations, all of which require Omega(n) running time. A basic primitive which underlies our first algorithm is Distance-2 coloring of the network. This primitive arises naturally in many applications such as broadcast scheduling and channel assignment. Minimizing the number of colors used in the coloring is very desirable for these applications, but this is known to be NP-hard. We present a fast distributed implementation of D2-coloring for ad hoc networks which is guaranteed to use at most O(1) times the number of colors required by the optimal algorithm. Our algorithms are geared towards constructing Well Connected Dominating Sets (WCDS) which have certain powerful and useful structural properties such as low size, low stretch and low degree. In this work, we also explore the rich connections between WCDS and routing in ad hoc networks. Specifically, we combine the properties of WCDS with other ideas to obtain the following interesting applications: * An online distributed algorithm for collision-free, low latency, low redundancy and high throughput broadcasting. * Distributed capacity preserving backbones for unicast routing and scheduling. Throughout this work, our focus is on obtaining distributed algorithms for ad hoc wireless networks with "provably good analytical we also explore the rich connections between WCDS and routing in ad hoc networks. Specifically, we combine the properties of WCDS with other ideas to obtain the following interesting applications: * An online distributed algorithm for collision-free, low latency, low redundancy and high throughput broadcasting. * Distributed capacity preserving backbones for unicast routing and scheduling. Throughout this work, our focus is on obtaining distributed algorithms for ad hoc wireless networks with "provably good analytical
  • No Thumbnail Available
    Item
    An Improved Approximation Algorithm For Vertex Cover with Hard Capacities
    (2003-04-04) Gandhi, Rajiv; Halperin, Eran; Khuller, Samir; Kortsarz, Guy; Srinivasan, Aravind
    In 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-30