Map labeling and its generalizations (2006)
Doddi, S., Marathe, M. V., Mirzaian, A., Moret, B. M. E., Zhou, B.
Scalability of ELISIMS: Comprehensive Detailed Simulation of the Electric Power Industry (2003)
L. J. Dowell, M. Drozda, D. B. Henderson, V. W. Loose, M. V. Marathe, D. J. Roberts
We conduct an experimental analysis to identify the most computational time consuming fragments of software and hardware that will likely be an integral part of power exchanges in a deregulated...
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...
M. V. Marathe, H. B. Hunt Iii, R. E. Stearns, V. Radhakrishnan
We study the complexity of various combinatorial problems when instances are specified using one of the following succinct specifications: (1) the 1-dimensional finite periodic narrow specifications...
Improving Spanning Trees by Upgrading Nodes (1998)
S. O. Krumke, M. V. Marathe, H. Noltemeir, R. Ravi, S. Ravi
Id: upgrade.tex,v 2.2 1997#09#18 13:14:08 krumke Exp wirth 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...
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...
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...
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...
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...
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...
Many birds with one stone: Multi-objective approximation algorithms (1994)
H. B. Hunt Iii, 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...
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, H. B. Hunt Iii, 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...
Upgrading Bottleneck Constrained Forests (1970)
S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi, H. -c. Wirth
. 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...