Publications | Computer Science and Computational Research

: Basic and Applied Simulation Science (CCS-5)

CCS Home >>> CCS-1 | CCS-2 | CCS-3 | CCS-4 | CCS-5

CCS-5 Home > Computer Science and Computational Research

Representative Publications

Computational Complexity Theory

"Theory of Periodically Specified Problems: Complexity and Approximability,"
M. V. Marathe, H. B. Hunt III, D. J. Rosenkrantz, and R. E. Stearns, in Proc.13th IEEE Conference on Computational Complexity, Buffalo, NY, (June 1998).

"The Complexity of Planar Counting Problems,"
H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, and R. E. Stearns, in SIAM J. Computing, 27(4), pp. 1142--1167 (August 1998).

"Complexity of Hierarchically and 1-Dimensional Periodically Specified Problems I: Hardness Results,"
M. V. Marathe, H. B. Hunt III, R. E. Stearns, and V. Radhakrishnan, in AMS-DIMACS Volume Series on Discrete Mathematics and Theoretical Computer Science; Workshop on Satisfiability Problem: Theory and Application, (35), pp. 225--259 (Nov. 1996).

"Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems,''
M. V. Marathe, H. B. Hunt III, R. E. Stearns, and V. Radhakrishnan, in SIAM J. Computing, 27(5), pp. 1237--1261, Oct. 1998. A Preliminary version titled "Approximation Schemes for PSPACE-Complete Problems for Succinct Specifications," appears in Proc. 26th Annual ACM Symposium on the Theory of Computing (STOC), Montreal, Canada, pp. 468--478 (May 1994).

"The Phase Transition in Random Horn Satisfiability and its Algorithmic Implications," G. Istrate, to appear in Random Structures and Algorithms .

"Algorithmic Implications of Phase Transitions," G. Istrate, in Proceedings of the 15'th annual Conference on Computational Complexity (CCC'00).

"On the Satisfiability of Random k-Horn Formulas," to appear in the proceedings of the DIMACS - Dimaitic Workshop on Graphs, Morphisms and Statistical Physics, P. Winkler et. al. (editors)

"The Phase Transition in 1-in-k SAT and NAE 3-SAT," D. Achlioptas, A. Chtcherba, G. Istrate, and C. Moore, in Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms (SODA'01).

Combinatorial Techniques in Data Mining

"Approximation Algorithms for Clustering to Minimize the Sum of Diameters,"
S. Doddi, M.V. Marathe, S.S. Ravi D. Taylor, and P. Widmayer, accepted for publication in Nordic Journal of Computing (August 2000).
Preliminary version appeared in Proc. 7th Scandinavian Workshop on Algorithm Theory, (SWAT) (July 2000) Bergen, Norway.

"Compact Location Problems with Budget and Communication Constraints,"
S.O. Krumke, H. Noltemeier, S.S. Ravi, and M.V. Marathe, invited paper in Theoretical Computer Science, 181(2), pp. 379--404 (July 1997).
Preliminary version appeared in 1st International Conference on Computing and Combinatorics, X'ian, China, LNCS Volume 959, Springer Verlag, pp. 510-519 (August 1995). Also invited for presentation at Computing and Combinatorics 95, Brest, France (August 1995).

"Budget Constrained Minimum Cost Connected Medians,"
G. Konjevod, S. Krumke, and M.V. Marathe, invited paper submitted to Journal of Discrete Algorithms. Preliminary version to appear in Proc. 26th International Workshop on Graph Theoretic Concepts in Computer Science, (WG), Konsantz, Germany (June 2000).