Network Dynamics and Simulation Science Laboratory [NDSSL]

Madhav V. Marathe

Deputy Director, Network Dynamics and Simulation Science Laboratory
Professor, Computer Science
Courtesy Appointment, Electrical and Computer Engineering

Professional Preparation

Los Alamos National Laboratory, Postdoctoral Associate, 1996.
University at Albany, State University of New York, Computer Science, PhD, 1994.
Indian Institute of Technology, Madras, Computer Science and Engineering, Bachelor of Technology, 1989.

Research Interests

Interaction-based modeling and simulation of large, complex biological, information, social, and technical (BIST) systems;
Design and analysis of algorithms and computational complexity;
Social networks, graph theory;
Wireless and next generation communication networks;
High performance and grid computing, especially pertaining to BIST systems; and
Computational epidemiology, computational economics.

Selected Publications

C. Barrett, K. Bisset, G. Konjevod, M. Marathe, and D. Wagner. Engineering Label-Constrained Shortest-Path Algorithms. In Proceedings of the Ninth DIMACS Implementation Challenge on Shortest Paths, 2008.
C. Barrett, K. Bisset, G. Konjevod, M. Marathe, and D. Wagner. Engineering Label-Constrained Shortest-Path Algorithms. In Proceedings of the Fourth International Conference on Algorithmic Aspects in Information and Management (AAIM 2008); June 2008; LNCS. Springer.
K. Atkins, C.L. Barrett, R. Beckman, K. Bisset, J. Chen, S. Eubank, A. Feng, X. Feng, S. Harris, B. Lewis, AVS Kumar, M. Marathe, A. Marathe, H. Mortveit, and P. Stretz. An Interaction Based Composable Architecture for Building Scalable Models of Large Social, Biological, Information and Technical Systems. CT Watch, 4, 2008:46-53.
Istrate, G., Marathe, M. and Ravi, S.S. Adversarial Scheduling Analysis of Game-Theoretic Models of Norm Diffusion. To appear in Computability in Europe 2008, Logic and Theory of Algorithms, 2008.
D. Chafekar, V.S. Kumar, M. Marathe, S. Parthasarathy and A. Srinivasan. Approximation Algorithms for Computing of Wireless Networks with SINR constraints. To appear in Proc. of INFOCOM, 2008.
C. Barrett, S. Eubank, B. Lewis, and M. Marathe. Information systems for detection and management of pandemics. In Encyclopedia of Geographic Information Systems, Shekhar S, Xiong X (eds). Springer-Verlag, In press 2008.
VSA Kumar, M. Marathe, S. Parthasarathy, and A. Srinivasan. Minimum weighted completion time. Encyclopedia of Algorithms, In press 2008.
K. Atkins, C. Barrett, R. Beckman, K. Bisset, J. Chen, S. Eubank, B. Lewis, A. Marathe, M. Marathe, H. Mortveit, P. Stretz, and A. Vullikanti. An analysis of layered public health interventions at Ft. Lewis and Ft. Hood during a pandemic influenza event. NDSSL Technical Report No. 07-019. 2007.
C. Barrett, B. Lewis, J. Chen, V.S. Anil Kumar, S. Eubank and M. Marathe. Interactions among human behavior, social networks, and societal infrastructures: A case study in computational epidemiology. In Ravi, S. and Shukla, S. (eds.), Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz. Springer Verlag, Vol. In press December 2007.
C. Barrett, H. Hunt III, M. Marathe, S.S. Ravi, D. Rosenkrantz, R.Stearns and M. Thakur. Predecessor existence problems for finite discrete dynamical systems. Theoretical Computer Science, 386(1-2), October 2007:3-37.
VSA Kumar, M. Marathe, A. S. Parthasarathy, and S. Zust. Scheduling on unrelated machines under tree-like precedence constraints. in special issue of Algorithmica containing selected papers from RANDOM 2007.
K. Atkins, C. Barrett, R. Beckman, K. Bisset, J. Chen, S. Eubank, V.S. Anil Kumar, B. Lewis, M. Macauley, A. Marathe, M. Marathe, H. Mortveit and P. Stretz. Simulated pandemic influenza outbreaks in Chicago: NIH DHHS Study Final report. NDSSL Internal Report No. 06-023. 2006.
K. Atkins, C. Barrett, R. Beckman, K. Bisset, J. Chen, S. Eubank, V.S. Anil Kumar, B. Lewis, A. Marathe, M. Marathe, H. Mortveit and P. Stretz. DTRA Alabama National Guard Study Capability Demonstration. NDSSL Internal Report No. 06-060. 2006.
C. Bailey-Kellog, N. Ramakrishnan, and M. Marathe. Spatial data mining to support pandemic preparedness. SIGKDD Explorations 8, 2006:80-82.
C.L. Barrett, K. Bisset, S. Eubank, V.S. Anil Kumar, M.V. Marathe and H.S. Mortveit Modeling and Simulation of Large Biological, Information and Socio-Technical Systems: An Interaction-Based Approach. Proceedings of the Short Course on Modeling and Simulation of Biological Networks, AMS Lecture Notes, Series: PSAPM, Springer Berlin Heidelberg, 2006:353-392.
C.. Barrett, H. Hunt III, M. Marathe, S.S. Ravi, D. Rosenkrantz, R. Stearns, and M. Thakur. Complexity of reachability problems for finite discrete dynamical systems. Journal of Computer and System Sciences, 72, 2006:1317-1345.
K. Bisset, K. Atkins, C. Barrett, R. Beckman, S. Eubank, A. Marathe, M. Marathe, H. Mortveit, P. Stretz, and A. Vullikanti. Synthetic data products for societal infrastructures and proto populations: Data set 1.0. NDSSL Technical Report No. 06-006. 2006.
H. B. Hunt, III, M. V. Marathe, and R. E. Stearns. The complexities of unquantified, quantified, and stochastic constrained satisfaction problems. in special issue of Discrete Applied Mathematics, 2006.
G. Istrate, M. Marathe and S. Ravi. Adversarial Scheduling analysis of iterated prisoner's dilemma game. NDSSL Technical Report #06-094. 2006.
VSA Kumar, S Parthasarathy, M.V. Marathe, A. Srinivasan, and S. Zust. Provable algorithms for parallel generalized sweep scheduling for unstructured meshes. Journal of Parallel and Distributed Computing 66: 2006:807-821.
C. Barrett, S. Eidenbenz, L. Kroc, M. Marathe and J. Smith. Parametric probabilistic routing in sensor networks. ACM/Baltzer J. Mobile Networks and Applications (MONET), 10(4), 2005:529-544.
S. Eubank, VS Anil Kumar, M. Marathe, A. Srinivasan, and N. Wang. Structure of social contact networks and their impact on epidemics. In Discrete Methods in Epidemiology, Abello J, Cormode, G (ed.). DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 70, 2006:179-185.
H.B. Hunt, III, M.V. Marathe, R.E. Stearns, and D.J. Rosenkrantz. Survey of periodically specified problems. In Computational Complexity and Statistical Physics, Istrate G, Moore C, Percus A (eds). Oxford University Press, Santa Fe Institute Lectures in the Sciences of Complexity, 2005.
E.L. Lloyd, R. Liu, M. Marathe, R. Ramanathan, and S. Ravi. Algorithmic aspects of topology control problems for ad hoc networks. ACM/Baltzer J Mobile Networks and Applications (MONET) 10, 2005:19-34.
VS Anil Kumar, M. Marathe, S. Parthasarathy, and A. Srinivasan. Algorithmic aspects of capacity in wireless networks. ACM SIGMETRICS Performance Evaluation Review 33(1), 2005:133-144.
H. Balakrishnan, C.L. Barrett, VSA Kumar, M.V. Marathe, and S. Thite. The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks. in special issue of IEEE Journal on Selected Areas in Communications 22 2005:1069-1079.
C. Barrett, S. Eubank, VSA Kumar, and M. Marathe. Understanding large scale social and infrastructure networks: a simulation based approach. Los Alamos National Laboratory, Technical Report No. LA-UR-04-1160, 2004.
C. Barrett, M. Drozda, M.V. Marathe, S.S. Ravi, and J. Smith. A mobility and traffic generation framework for modeling and simulating ad hoc communication networks. to appear in special issue of Scientific Programming containing selected papers presented at the 6th ACM Symposium on Applied Computing (SAC) special track on Simulations of Discrete Entities 12: 2005:1-23
C.L. Barrett, M.V. Marathe, D.C. Engelhart, and A. Sivasubramaniam. Approximate connectivity graph generation in mobile ad hoc radio networks. to appear in a special issue of Elsevier Journal of Systems and Software, containing selected papers presented at the 36th IEEE Annual Simulation Symposium, 73 2005:63-74.
S. Eubank, H. Guclu, VS Anil Kumar, MV Marathe, A Srinivasan, Z Toroczkai, and N Wang. Modelling disease outbreaks in realistic urban social networks. Nature, 429(6998), 2004:180-184.
G. Konjevod, S. Krumke, and M. Marathe. Budget constrained minimum cost connected medians. containing selected papers presented at the 26th International Workshop on Graphic Theoret, 2 2004:453-469.
M.V. Marathe, L.D. Risenger, and A. Panconesi. Experimental analysis of a simple distributed edge coloring algorithm. Journal of Experimental Algorithmics, 9, 2004:1-23.
K. Atkins, C. Barrett, R. Beckman, K. Bisset, M. Drozda, S. Eubank, C. Engelhart, N. Hengartner, G. Istrate, A. Kumar, M.V. Marathe, M. Morin, C. Reidys, S. Ravi, P. Romero, R. Pistone, S. Pathak, J. Smith, P. Stretz, and S. Zust. AdHopNET: Integrated tool for end-to-end analysis of extremely large next generation communication networks, Volume I & II. Los Alamos National Laboratory, Technical Report Nos. LA-UR-03-2076 and LA-UR-03-2077, 2003.
C. Barrett, K. Bisset, M.V. Marathe, H. Mortveit and C. Reidys. Design, specification and analysis of ad-hoc networks. Los Alamos National Laboratory, Technical Report No. LA-CP-03-0148, 2003.
C. Barrett, D. Cook, V. Faber, G. Hicks, M.V. Marathe, A. Marathe, A. Srinivasan, Y.J. Sussmann, and H. Thornquist. Statistical analysis of algorithms: A case study of market-clearing mechanisms in the power industry. Journal of Graph Algorithms and Applications (JGAA), 7, 2003:3-31.
C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, and R.E. Stearns. Reachability Problems for Sequential Dynamical Systems with Threshold Functions. Theoretical Computer Science 295(1-3), February 2003:41-64.
C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, and R.E. Stearns. On Some Special Classes of Sequential Dynamical Systems. Accepted, Annals of Combinatorics, March, 2003.
C. Barrett C and M.V. Marathe. Foundations of Simulation Science. Los Alamos National Laboratory, Technical Report , 2003.
C. Burch, R. Carr, S. Krumke, M. Marathe, C. Phillips, and E. Sundberg. A decomposition-based pseudoapproximation algorithm for network flow inhibition. In Network Interdiction and Stochastic Integer Programming, Woodruff DL (ed), Vol. 22, 1, pp 51-68. Kluwer Academic Press, 2003.
S. Doddi, M.V. Marathe, and B. Moret. Point set labeling with specified positions. in special issue of International Journal of Computational Geometry, containing selected papers presented at ACM Symposium on Computational Geometry (SoCG), 12, 2003:29-66.
H. B. Hunt, III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D. Rosenkrantz, and R. Stearns. Parallel approximation schemes for a class of planar and near planar combinatorial problems. Information and Computation, 173, 2002:40-63.
S.R. Arikati, A. Dessmark, A. Lingas, and MV Marathe. Approximation algorithms for maximum two-dimensional pattern matching. Theoretical Computer Science, 255, 2001:51-62.
C. Barrett, R. Jacob, and M.V. Marathe. Formal Language Constrained Path Problems. SIAM J. Computing, 30(3) 2001: 809–837.
C. Barrett, A. Marathe and M. Marathe. Parameterized scalable models for simulating deregulated electric power industry. Los Alamos National Laboratory, Technical Report, 2001.
C. Barrett, M. Marathe, and C. Reidys. Commercial prospects for mobile communications from the developments in large scale infrastructure simulation technology. Final Report, CRADA Agreement with Motorola, 2001.
C. Barrett, M. Marathe, C. Reidys, S. Ravi, and J. Smith. Ad-hopNET: A large scale simulation based analysis of ad hoc networks, A seedling study for DARPA. Los Alamos National Laboratory, Technical Report No. LA-UR-01-1644, 2001.
S.O. Krumke, M. V. Marathe, and B. Moret. Models and approximation algorithms for channel assignment in radio networks. in special issue of Wireless Journal, containing selected papers presented at the 2nd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), 7, 2001:575-584.
S.O. Krumke, M.V. Marathe, H. Noltemeier, S.S. Ravi, and H.C. Wirth. Upgrading bottleneck constrained forests. Discrete Applied Mathematics,108, 2001:129-142.
R. Ravi, M.V. Marathe, S.S. Ravi, D. J. Rosenkrantz, H.B. Hunt III. Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica, 31, 2001:58-78.
C.L. Barrett, R.J. Beckman, K.P. Berkbigler, K.R. Bisset, B.W. Bush, S. Eubank, J.M. Hurford, G. Konjevod, D.A. Kubicek, M.V. Marathe, J.D. Morgeson, M. Rickert, P.R. Romero, L.L. Smith, M.P. Speckman, P.L. Speckman, P. Stretz, G.L. Thayer, and M.D. Williams. TRANSIMS, Version TRANSIMS-LANL-1.1 Volumes 1-6. In Los Alamos technical report LA-UR-00-1724, 1766, 1755, 1767 (ed.), 2001.
D. Cook, V. Faber, G. Hicks, and M.V. Marathe. Combinatorial Problems Arising in Deregulated Electrical Power Industry: Survey and Future Directions. In Proc. Approximation and Complexity in Numberical Optimization: Continuous and Discrete Problems, Pardalos PM (ed), 2000:138-162. Kluwer Academic Publishers.
S. Doddi, M.V. Marathe, R. Ravi, D. Taylor, and P. Widmayer. Approximation algorithms for clustering to minimize the sum of diameters. invited paper appears in the special issue of Nordic Journal of Computing, 7(3), 2000:185-203.
H.B. Hunt, III, R. Stearns, and M. Marathe. Relational representability, local reductions, and the complexity of generalized satisfiability problems. Los Alamos National Laboratory, Technical Report No. LA-UR-006108, 2000.
H.B. Hunt, III, R. Stearns, and M.V. Marathe. (2000) On the efficient approximability of "Hard" problems: a survey In Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, Pardalos PM (ed), Vol. 42, 200:308-322. Kluwer Academic Publishers.
R. Jacob, M. Marathe, and K. Nagel. A computational study of routing algorithms for realistic transportation networks. J Exp Algorithmics, 4 Article 6.
S.O. Krumke, M.V. Marathe, H. Noltemeier, R. Ravi, S.S. Ravi, R. Sundaram and H.C. Wirth. Improving minimum cost spanning trees by upgrading nodes. Journal of Algorithms, 33 1999:92-111.
S.O. Krumke, H. Noltemeier, H-C Wirth, M.V. Marathe, R. Ravi, S.S. Ravi, and R. Sundaram. Improving spanning trees by upgrading nodes. Theoretical Computer Science, 221, 1999:139-155
Marathe M, Hunt III H, Radhakrishnan V, Stearns R (1998) Approximation algorithms for PSPACE-hard hierarchically and periodically specified problems. SIAM Journal on Computing, 27(5), 1998:1237-1261.
Marathe MV, Ravi R, Sundaram R, Ravi SS, Rosenkrantz DJ, Hunt III HB Bicriteria network design problems. J. Algorithms, 28(1), 1998:142-171.

(Last updated: Tue Feb 26 13:19:38 EST 2008)