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 (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 (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...
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]....
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...
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...