Browsing by Author "Srinivasan, Aravind"
Now showing 1 - 7 of 7
Results Per Page
Sort Options
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 Distributed Strategies for Channel Allocation and Scheduling in Software-defined Radio Networks(2008-01-14) Han, Bo; Kumar, V. S. Anil; Marathe, Madhav; Parthasarathy, Srinivasan; Srinivasan, AravindEquipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple nonoverlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good (centralized and distributed) algorithms for simultaneous channel allocation of individual links and packet-scheduling, in Software- Defined Radios (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters’ decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductivescheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.Item Efficient Lookup on Unstructured Topologies(2006-03-02T17:22:28Z) Morselli, Ruggero; Bhattacharjee, Bobby; Marsh, Michael A.; Srinivasan, AravindWe present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT). We present analytic bounds for the worst-case performance of our protocol. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size.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 Modelling disease outbreaks in realistic urban social networks(2004) Eubank, Stephen; Guclu, Hasan; Kumar, V.S. Anil; Marathe, Madhav; Srinivasan, Aravind; Toroczkai, Zoltan; Want, NanHere we present a highly resolved agent-based simulation tool (EpiSims), which combines realistic estimates of population mobility,based on census and land-use data, with parameterized models for simulating the progress of a disease within a host and of transmission between hosts10. The simulation generates a largescale,dynamic contact graph that replaces the differential equations of the classic approach. EpiSims is based on the Transportation Analysis and Simulation System (TRANSIMS) developed at Los Alamos National Laboratory, which produces estimates of social networks based on the assumption that the transportation infrastructure constrains people’s choices about where and when to perform activities11. TRANSIMS creates a synthetic population endowed with demographics such as age and income, consistent with joint distributions in census data. It then estimates positions and activities of all travellers on a second-by-second basis. For more information on TRANSIMS and its availability, see Supplementary Information. The resulting social network is the best extant estimate of the physical contact patterns among large groups of people—alternative methodologies are limited to physical contacts among hundreds of people or non-physical contacts (such as e-mail or citations) among large groups.Item Ranking Search Results in Peer-to-Peer Systems(2006-01) Gopalakrishnan, Vijay; Morselli, Ruggero; Bhattacharjee, Bobby; Keleher, Peter; Srinivasan, AravindP2P deployments are a natural infrastructure for building distributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them. Users, however, are primarily interested in the most relevant, and not all possible results. Using random sampling, we extend a class of well-known information retrieval ranking algorithms such that they can be applied in this distributed setting. We analyze the overhead of our approach, and quantify exactly how our system scales with increasing number of documents, system size, document to node mapping (uniform versus non-uniform), and types of queries (rare versus popular terms). Our analysis and simulations show that a) these extensions are efficient, and can scale with little overhead to large systems, and b) the accuracy of the results obtained using distributed ranking is comparable to a centralized implementation.Item Scalable Resilient Media Streaming(2003-06-04) Banerjee, Suman; Braud, Ryan; Lee, Seungjoon; Bhattacharjee, Bobby; Srinivasan, AravindWe present a low-overhead media streaming system, called SRMS (Scalable Resilient Media Streaming) that can be used to scalably deliver streaming data to a large group of receivers. SRMS uses overlay multicast for data distribution to a large group of users. SRMS leverages a probabilistic loss recovery technique to provide high data delivery guarantees even under large network losses and overlay node failures. Through detailed analysis in this paper, we show that this loss recovery technique (and consequently SRMS) has efficient scaling properties --- the overheads at each overlay node asymptotically decrease to zero with increasing group sizes. We also present a detailed description of the SRMS architecture. The clients in the SRMS system are able to interoperate with existing media streaming servers that use RTP for data transport. One of the interesting features of SRMS is that it can simultaneously support clients with disparate access bandwidths. It enables the necessary bandwidth adaptations using standard Real-time Transport Protocol (RTP) mechanisms, e.g. RTP translators. We have implemented and evaluated the SRMS system in detail on an emulated network as well as on a wide-area testbed with up to 128 clients. Our results show that clients using SRMS achieve high (> 97%) data delivery ratios with low overheads (< 5%) even for very high failure rates (upto five per minute). (UMIACS-TR-2003-51)