Adversarial Scheduling Analysis of Game Theoretic Models of Norm Diffusion (2008)
Istrate, Gabriel, Marathe, Madhav V., Ravi, S. S.
In (Istrate, Marathe, Ravi SODA 2001) we advocated the investigation of robustness of results in the theory of learning in games under adversarial scheduling models. We provide evidence that such an...
A mathematical formalism for agent-based modeling (2007)
Laubenbacher, Reinhard, Jarrah, Abdul S., Mortveit, Henning, Ravi, S. S.
Many complex systems can be modeled as multiagent systems in which the constituent entities (agents) interact with each other. The global dynamics of such a system is determined by the nature of the...
Budgeted Maximum Graph Coverage (2002)
Sven Oliver Krumke, Madhav V. Marathe, Diana Poensgen, S. S. Ravi
An instance of the maximum coverage problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total...
Algorithmic Aspects of Topology Control Problems for Ad hoc Networks (2002)
Errol L. Lloyd, Rui Liu, Madhav V. Marathe, Ram Ramanathan, S. S. Ravi
Topology control problems are concerned with the assignment of power values to the nodes of an ad~hoc network so that the power assignment leads to a graph topology satisfying some specified...
Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems (2001)
R. Ravi, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz
We study network-design problems with two different design objectives: the total cost of the edges and nodes in the network and the maximum degree of any node in the network. A prototypical example...
Sven O. Krumke, Madhav V. Marathe, S. S. Ravi
this paper, we consider the channel assignment problem for transmitters. The transmission of a station T is intended for and must be received collision-free by all the neighbors of T (i.e., the...
Approximation Algorithms for Certain Network Improvement Problems (2000)
Sven O. Krumke, R. Ravi, S. S. Ravi
. We study budget constrained network upgrading problems. Such problems aim at nding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an...
Approximation Algorithms for Channel Assignment in Radio Networks (2000)
Sven O. Krumke, Madhav V. Marathe, S. S. Ravi
We consider the channel assignment (broadcast scheduling) problem for packet radio networks. Such networks are naturally modeled by graphs with certain geometric structure. The channel assignment...
Modifying Edges of a Network to Obtain Short Subgraphs (2000)
Kay U. Drangmeister, Sven O. Krumke, Madhav V. Marathe, Hartmut Noltemeier, S. S. Ravi
This paper considers problems of the following type: We are given an edge weighted graph G = (V; E). It is assumed that each edge e of the given network has an associated function c e that species...
Improving Minimum Cost Spanning Trees by Upgrading Nodes (1999)
S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, ...
We study budget constrained network upgrading problems. We are given an undirected edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v). This upgrade reduces the weight...
Modifying Edges of a Network to Obtain Short Subgroups (1998)
K. U. Drangmeister, S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi
This paper considers problems of the following type: We are given an edge weighted graph G =#V;E#. It is assumed that each edge e of the given network has an associated function c e that speci#es the...
Upgrading Bottleneck Constrained Forests (1998)
S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi
. We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v). This upgrade reduces the delay of each...
Bicriteria Network Design Problems (1998)
Marathe, Madhav V., Ravi, R., Sundaram, Ravi, Ravi, S. S., Rosenkrantz, Daniel J., Hunt III, Harry B.
We study a general class of bicriteria network design problems. A generic problem in this class is as follows: Given an undirected graph and two minimization objectives (under different cost...
Improving Spanning Trees by Upgrading Nodes (1998)
M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, H. C. Wirth
. We study budget constrained optimal network upgrading problems. We are given an edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v). This upgrade reduces the delay of...
Alarm Placement in Systems with Fault Propagation (1998)
K. B. Lakshmanan, Daniel J. Rosenkrantz, S. S. Ravi
this paper, we consider systems that can be modeled as directed
Approximation Algorithms for Certain Network Improvement Problems (1998)
Sven O. Krumke, R. Ravi, S. S. Ravi
We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an...
Modifying Networks to Obtain Low Cost Trees (1998)
S. O. Krumke, H. Noltemeier, M. V. Marathe, S. S. Ravi, K. U. Drangmeister
We consider the problem of reducing the edge lengths of a given network so that the modified network has a spanning tree of small total length. It is assumed that each edge e of the given network has...
Complexity and Approximability of Certain Bicriteria Location Problems (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
. We investigate the complexity and approximability of some location problems when two distance values are specified for each pair of potential sites. These problems involve the selection of a...
Compact Location Problems (1998)
S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz
We consider the problem of placing a specified number (p) of facilities on the nodes of a network so as to minimize some measure of the distances between facilities. This type of problem models a...
Compact Location Problems with Budget and Communication Constraints (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
. We consider the problem of placing a specified number p of facilities on the nodes of a given network with two nonnegative edge-- weight functions so as to minimize the diameter of the placement...
Compact Location Problems (1998)
S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz
We consider the problem of placing a specified number (p) of facilities on the nodes of a network so as to minimize some measure of the distances between facilities. This type of problem models a...
Complexity and Approximability of Certain Bicriteria Location Problems (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
. We investigate the complexity and approximability of some location problems when two distance values are specified for each pair of potential sites. These problems involve the selection of a...
Compact Location Problems with Budget and Communication Constraints (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
. We consider the problem of placing a specified number p of facilities on the nodes of a given network with two nonnegative edge-- weight functions so as to minimize the diameter of the placement...
Bicriteria Compact Location Problems (1998)
Sven O. Krumke, H. Noltemeier, S. S. Ravi, Madhav V. Marathe
We investigate the complexity and approximability of some location problems when two distance values are specified for each pair of potential sites. These problems involve the selection of a...
Modifying Networks to Obtain Low Cost Trees (1998)
S. O. Krumke, H. Noltemeier, M. V. Marathe, S. S. Ravi, K. U. Drangmeister
We consider the problem of reducing the edge lengths of a given network so that the modified network has a spanning tree of small total length. It is assumed that each edge e of the given network has...
Improving Spanning Trees by Upgrading Nodes (1998)
M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, H. C. Wirth
. We study budget constrained optimal network upgrading problems. We are given an edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v). This upgrade reduces the delay of...
Compact Location Problems (1998)
S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz
We consider the problem of placing a specified number (p) of facilities on the nodes of a network so as to minimize some measure of the distances between facilities. This type of problem models a...
Complexity and Approximability of Certain Bicriteria Location Problems (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
. We investigate the complexity and approximability of some location problems when two distance values are specified for each pair of potential sites. These problems involve the selection of a...
Bicriteria Compact Location Problems (1998)
Sven O. Krumke, H. Noltemeier, S. S. Ravi, Madhav V. Marathe
We investigate the complexity and approximability of some location problems when two distance values are specified for each pair of potential sites. These problems involve the selection of a...
Compact Location Problems with Budget and Communication Constraints (1998)
S. O. Krumke, H. Noltemeier, S. S. Ravi, M. V. Marathe
. We consider the problem of placing a specified number p of facilities on the nodes of a given network with two nonnegative edge-- weight functions so as to minimize the diameter of the placement...
Parallel Approximation Schemes for Planar and Near-Planar Satisfiability and Graph Problems (1997)
Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, Richard E. Stearns
We present parallel approximation schemes for a large class of satisfiability and graph problems for planar and almost planar instances. Problems considered in this paper include optimization...
We present a uniform approach for proving the polynomial time decidability of various simulation and equivalence relations for finite state processes. Our approach applies directly to a number of...
Using Active Clients to Minimize Replication in Primary-Backup Protocols (1996)
Parvathi Chundi, Ragini Narasimhan, Daniel J. Rosenkrantz, S. S. Ravi
We consider the primary backup-approach for providing fault-tolerant services in a distributed system. In this approach, a fault-tolerant service is implemented using a collection of servers. One of...
Deferred Updates and Data Placement in Distributed Databases (1996)
Parvathi Chundi, Daniel J. Rosenkrantz, S. S. Ravi
Commercial distributed database systems generally support an optional protocol that provides loose consistency of replicas, allowing replicas to be inconsistent for some time. In such a protocol,...
Deferred Update Protocols for Multi-Site Transactions (1996)
Parvathi Chundi, Daniel J. Rosenkrantz, S. S. Ravi
Several commercial distributed database systems provide an optional protocol that defers updates of replicas in order to attain higher transaction throughput. Each replicated data item is assigned a...
Algorithms for Alarm Placement in Systems with Fault Propagation (1995)
In this paper, we consider systems that can be modeled as directed acyclic graphs such that nodes represent components and directed edges represent fault propagation between components. Some...
H. B. Hunt, Iii M. V, Marathe V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz, R. E. Stearns
We present parallel approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner [CCJ90, MHR92, Te91]....
Spanning trees short or small (1994)
Ravi, R., Sundaram, R., Marathe, Madhav V., Ravi, S. S., Rosenkrantz, Daniel J.
We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number $k$ of nodes are required to be connected in...
The complexity of approximating PSPACE-Complete problems for hierarchical specifications (1994)
Marathe, Madhav V., Hunt III, Harry B., Ravi, S. S.
We extend the concept of polynomial time approximation algorithms to apply to problems for hierarchically specified graphs, many of which are PSPACE-complete. Assuming P != PSPACE, the existence or...
Geometry based heuristics for unit disk graphs (1994)
Marathe, Madhav V., Breu, H., Hunt III, Harry B., Ravi, S. S., Rosenkrantz, Daniel J.
Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk...
Many birds with one stone: Multi-objective approximation algorithms (1994)
R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz
We study network-design problems with multiple design objectives. In particular, we look at two cost measures to be minimized simultaneously: the total cost of the network and the maximum degree of...
Hierarchically Specified Unit Disk Graphs (1970)
Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi
We characterize the complexity of a number of basic optimization problems for unit disk graphs specified hierarchically as in [BOW83, LW87a, Le88, LW92]. Both PSPACE-hardness results and polynomial...
Compact Location Problems (1970)
S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz
We consider the problem of placing a specified number (p) of facilities on the nodes of a network so as to minimize some measure of the distances between facilities. This type of problem models a...
Simple Heuristics for Unit Disk Graphs (1970)
M. V. Marathe, H. Breu, S. S. Ravi, D. J. Rosenkrantz
Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk...
On Approximation Algorithms for the Minimum Satisfiability Problem (1970)
this paper, our focus is on deterministic approximation algorithms for the MINSAT problem. From now on, we will use the word `heuristic' to mean a deterministic approximation algorithm which runs in...
Improving Minimum Cost Spanning Trees by Upgrading Nodes (1970)
S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi, S. S. Ravi, R. Sundaram, ...
We study budget constrained network upgrading problems. We are given an undirected edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v). This upgrade reduces the weight...
Approximation Algorithms for Certain Network Improvement Problems (1970)
Sven O. Krumke, R. Ravi, S. S. Ravi
. We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given...
Upgrading Bottleneck Constrained Forests (1970)
S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi
. We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V; E) where node v 2 V can be upgraded at a cost of c(v). This upgrade reduces the delay of each...
Spanning Trees Short Or Small (1970)
R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz, S. S. Ravi
We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number k of nodes are required to be connected in...
Approximation Algorithms for Clustering to Minimize the Sum of Diameters (1970)
Srinivas R. Doddi, Madhav V. Marathe, S. S. Ravi, David Scot Taylor
. We consider the problem of partitioning the nodes of a complete edge weighted graph into k clusters so as to minimize the sum of the diameters of the clusters. Since the problem is NP-complete, our...
Adversarial scheduling analysis of Game-Theoretic Models of Norm Diffusion.
Istrate, Gabriel, Marathe, Madhav V., Ravi, S.S.
In (Istrate et al. SODA 2001) we advocated the investigation of robustness of results in the theory of learning in games under adversarial scheduling models. We provide evidence that such an analysis...