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...
Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems (1998)
Marathe, Madhav V., Hunt III, Harry B., Stearns, Richard E., Radhakrishnan, Venkatesh
We study the efficient approximability of basic graph and logic problems in the literature when instances are specified hierarchically as in \cite{Le89} or are specified by 1-dimensional finite...
The Complexity of Planar Counting Problems (1998)
Hunt III, Harry B., Marathe, Madhav V., Radhakrishnan, Venkatesh, Stearns, Richard E.
We prove the #P-hardness of the counting problems associated with various satisfiability, graph and combinatorial problems, when restricted to planar instances. These problems include...
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...