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.

Awards

University at Albany, Distinguished Alumni Award 2004.
Los Alamos National Laboratory Achievement Award 2004.
Distinguished Copyright award for TRANSIMS software 1999.
National Talent Search Scholarship, Government of India, 1985-89.
Ranked 66th in the Indiana Institute of Technologies Joint Entrance Exam, 1985.

Professional Activities

External Advisory Board, National Center for Advanced Secure Systems (NCASSR) at NCSA, Illinois, Sept 2004-2008.
Member, LANL, Institutional Computing (ICTC) Committee, September 2002- December 2004
Invited participant in NSF sponsored workshops titled Bridging the Gap between Wireless Networking and Advances at Physical Layer, August 2007 Mobility in Wireless Networks – Challenges and Opportunities July 2007, Modeling Social Dynamics Workshop, October 2006.
Member Recruitment committee, CIC Division, Los Alamos National Laboratory, Fall 1997 - Dec 1999.
Co-Organizer: Agent Based Modeling and Simulation Workshop at Institute of Mathematics and its Applications, November, 2003.
Member Review Committee, Los Alamos Computer Science Institute, September 2001.
Member, Laboratory Directed Research and Development (Mathematics and Computational Science) Review Committee, May 1998 - April 2000.

Selected Case Studies

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 military preparedness during a pandemic influenza event. NDSSL Technical Report No. 07-019. 2007.
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 Military Preparedness Capability Demonstration. NDSSL Internal Report No. 06-060. 2006.
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.
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.
Anson, D., Barrett, C., Marathe, M., Nagel, K., Rickert, M., & Stein, M. Engineering the Route Planner for the Dallas Case Study: Los Alamos National Laboratory Technical Report LAUR-No-97-1331, , 1997.

Selected Presentations

M. Marathe Decision & Policy Informatics for Large Co-evolving Socio-Technical Networks. Presented to Harvard University, May 2009.
M. Marathe, Chris Barrett & Stephen Eubank Decision and Policy Informatics for Large Co-evolving Socio-Technical Networks. Presented at 4th International Conference on Critical Infrastructures, April 2009.
M. Marathe Co-evolving Complex Networks: Epidemics in Social and Wireless Networks. Invited Presentation to SIAM Conference on Computational Science and Engineering (CSE09), Miami, Florida, February 20, 2009.
M. Marathe Computational Epidemiology: An Interaction Based Approach. Invited Presentation to National Institute of Virology, Pune, India, February 2008.
M. Marathe Building Virtual Cities: Computational Aspects of Modeling Large Societal Infrastructure Systems. Invited Colloquium, School of Computing and Indian Institute of Technology (IIT), Bombay, India, February 2008.
M. Marathe Coupled and Co-evolving Social and Telecommunication Networks. Invited Presentation to Frontiers in Transportation Social Interactions Amsterdam, Netherlands, October 14-16, 2007.
M. Marathe Deriving Mobility Models from Principles and their Applications. Invited Presentation to NSF Mobility in Wireless Networks Workshop, North Brunswick, NJ July 31-August 1, 2007.
M. Marathe An Integrated Approach to Computing Capacity and Developing Cross Layer Protocols for Wireless Networks. Invited Presentation to NSF NeTS PI meeting , Chicago, IL, July 11-13, 2007.
M. Marathe Algorithmic Considerations in Modeling and Simulation of Large Societal Infrastructures. Invited Presentation to 2007 Ninth Workshop on Algorithm Engineering and Experiments (ALENEX) New Orleans, Louisiana, January 6, 2007.
M. Marathe Computational Considerations in the Study of Real Very Large Complex Networks. Invited Presentation to NCSA, Age of Networks Seminar Series, October 2006.
M. Marathe Interaction Based Computer Modeling for Comprehensive Incident Characterization to Support Pandemic Preparedness. Invited Presentation to Spatial Data Mining: Consolidation and Renewed Bearing (SIAM-DM 06), April 22, 2006.
M. Marathe Routing in Very Large Multi-Modal Time Dependent Networks: Theory and Practice. Invited Presentation to Algorithmic Methods and Models for Optimization of RailwayS ATMOS Malaga, Spain, July 13, 2002.
M. Marathe Towards a Predictive Computational Complexity Theory. Invited Presentation to International Colloquium on Automata, Languages and Programming (ICALP), Malaga 2002.

Selected Publications

2009

K. Channakeshava, D. Chafekar, K. Bisset, VS Anil Kumar, and M. Marathe EpiNet:A Simulation Framework to Study the Spread of Malware in Wireless Networks In Proceedings 2nd International Conference on Simulation Tools & Techniques (SIMUTools'09), 2009.
V.S. Anil Kumar ,M. Marathe, S. Parthasarathy and A.Srinivasan Scheduling on Unrelated Machines Accepted for publication in JACM , Forthcoming 2009.
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.XXII 2009.
K. Bisset, J. Chen, X. Feng, VS Anil Kumar and M. Marathe. EpiFast: A fast algorithm for large scale realistic epidemic simulations on distributed memory systems In Proceedings of 23rd ACM International Conference on Supercomputing (ICS'09) , 2009:430-439.
C. Barrett, K. Bisset, J. Leidig, A. Marathe and M. Marathe. Estimating the Impact of Public and Private Strategies for Controlling an Epidemic: A Multi-Agent Approach In Proceedings of 21st Innovative Applications of Artificial Intelligence Conference, Pasadena, CA, Forthcoming 2009.
M. Khan, VS Kumar, M. Marathe, G. Pandurangan and SS Ravi. Approximation Algorithms for Power-Efficient and Low-Interference Topology Control in Unreliable Ad hoc Networks In 28th Conference on Computer Communications (INFOCOM> In press 2009.
B. Han, VS Anil Kumar, M Marathe, S. Parthasarthy, A. Srinivasan. Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks. Proceedings of INFOCOM, 2009, 28th Conference of Computer Communications 2009:1521-1529.
2008
D. Chafekar, D. Levin, V.S. Anil Kumar, M. Marathe, S. Parthasarathy and A. Srinivasan. Capacity of asynchronous Random-Access Scheduling in Wireless Networks. Proceedings of INFOCOM, 2008, 27th Conference of Computer Communications, 1148-1156.
D. Chafekar, V.S. Anil Kumar, M. Marathe, S. Parthasarathy and A. Srinivasan. Approximation Algorithms for Computing Capacity of Wireless Networks with SINR constraints. Proceedings of INFOCOM, 2008, 27th Conference of Computer Communications, 1166-1174.
C. Barrett, K. Bisset, S. Eubank, X. Feng and M. Marathe. EpiSimdemics: an Efficient and Scalable Framework for Simulating the Spread of Infectious Disease on Large Social Networks. In Proceedings of the 2008 ACM/IEEE conference on Supercomputing.
C. Barrett, S. Eubank and M. Marathe. An interaction-based approach to computational epidemiology. In 23rd AAAI Conference on Artificial Intelligence, 2008.
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:1-10.
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. Proceedings of the 4th Conference on Computability in Europe: Logic and Theory of Algorithms, Lecture Notes in Computer Science,5028, 2008:273-282.
D. Chafekar, D. Levin, V.S. Anil Kumar, M. Marathe, S. Parthasarathy and A. Srinivasan. Capacity of asynchronous Random-Access Scheduling in Wireless Networks. Proceedings of INFOCOM, 2008, 27th Conference of Computer Communications, 1148-1156.
D. Chafekar, V.S. Anil Kumar, M. Marathe, S. Parthasarathy and A. Srinivasan. Approximation Algorithms for Computing Capacity of Wireless Networks with SINR constraints. Proceedings of INFOCOM, 2008, 27th Conference of Computer Communications, 1166-1174.
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, 2008:1-99, Springer.
S. Eubank, AVS Kumar, and M. Marathe. Epidemiology and wireless communication tight analogy or loose metaphor. In Bio-Inspired Computing and Communication Springer Verlag, 2008:91-104.
D. Chafekar, VS Anil Kumar, M. Marathe and S. Parthasarathy. Power Efficient Throughput Maximization in Multi hop Wireless Networks. Proceedings of IEEE Globecom 2008 Wireless Networking Symposium (GC'08), 2008:1-6.
VS Anil Kumar, M. Marathe, S. Premaraju and I. Pirwani. On the Complexity of Minimum Partition of Frequency-Agile Radio Networks. 3rd IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks, 2008:1-10.
2007
D. Chafekar, V.S. Anil Kumar, M. Marathe, S. Parathasarathy and A. Srinivasan. Cross-Layer latency minimization for wireless networks with SINR constraints. Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, 2007:110-119.
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.
C. Barrett, K. Bisset, J. Chen, B. Lewis, S. Eubank, VS. Anil Kumar, M. Marathe, H. Mortveit. Effect of Public Policies and Individual Behavior on the Co-evolution of Social Networks and Infectious Disease Dynamics. Proceedings of DIMACS/DyDAn Workshop on Computational Methods for Dynamic Interaction Networks, September 2007.
VS Anil Kumar, M. Marathe, S. Parthasarathy, A. Srinivasan. Provable algorithms for joint optimization of transport, routing and MAC layers in wireless ad hoc networks. Proceedings of Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM)-Principles of Mobile Computing (POMC), 2007.
R. Thomas, L. DaSilva, M. Marathe, and K. Wood. Critical Design Decisions for Cognitive Networks. Proceedings of ICC Wireless Adhoc and Sensor Networks Symposium, 2007.
C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, and M.Thakur. Computational Aspects of Analyzing the Social Network Dynamics Proceedings of International Joint Conference on Artifical Intelligence, (IJCAI 07), Hyderabad, India 2007:2268-2273.
2006
C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns. Dichotomy Results for Reachability Problems in Sequential Dynamical Systems J. Computer and System Science, 72(8), 2006:1317-1345.
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.L. Barrett, H.B. Hunt, III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, and M. Thakur. Computational Complexity of Analyzing the Dynamic Reliability of Interdependent Infrastructures. Proceedings of 3rd International Conference on Critical Infrastructures (CRIS06), August 2006.
V.S. Anil Kumar, M. Marathe, M. Thakur, R. Sundaram and S. Thulasidasan. Scaling Laws for the Internet over Urban Regions CAIDA (Cooperative Association for Internet Data Analysis), ISMA 2006 WIT: Workshop on the Internet Topology, 2006.
J. Chen, M.V. Marathe, R. Rajaraman and R. Sundaram Semantic Compression of TPC Traces Proceedings of IEEE International Conference on Distributed Computing Systems (ICDCS), 2006.
C. Barrett, G. Istrate, V.S. Anil Kumar, M. Marathe, S. Thite and S. Thulasidasan. Strong Edge Coloring for Channel Assignment in Wireless Radio Networks Proceedings of the First IEEE International Workshop on Foundations and Algorithms for Wireless Network (FAWN’06) 2006:106-110. C. Barrett, S. Eubank and M. Marathe. < a href=” http://www.springerlink.com/content/v103u4185k703457/”target=”new”>Modeling and Simulation of Large Biological, information and Socio-Technical Systems: An Interaction Based Approach In Interactive Computing: A New Paradigm. D. Goldin, S. Smolka and P. Wegner (eds), Springer Verlag, 2006: 353-394.
2005
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.
V.S.A Kumar, M. Marathe, S. Parthasarathy and A. Srinivasan. Approximation Algorithms for Scheduling on Multiple Machines Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05),, 2005:254-263.
C. Barrett, S. Eidenbenz, L. Kroc, M. Marathe and J. Smith. Probabilistic Multi-path v. Deterministic Single-Path Protocols for Dynamic Ad-Hoc Network Scenarios. ACM Symposium on Applied Computing (SAC), 2005:1166-1173.
C. Barrett, M. Morin, C. Engelhart, M. Marthe, J. Smith, M. Drozda and V. Anil Kumar. Understanding Protocol Performance and Robustness of Ad-Hoc Networks Through Structural Analysis Proceedings of IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), 2005. HB. Hunt III, M. Marathe, R Stearns, and DJ Rosenkrantz. A Survey of Periodically Specified Problems. In Computational Complexity and Statistical Physics, G. Istrate, C. Moore and A. Percus (eds) Oxford University Press, 2005: 285-318.
2004
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.
S. Eubank, V. Anil Kumar, M. Marathe, A. Srinivasan, and N. Wang. Structural and Algorithmic Aspects of Massive Social Networks. Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004:718-727.
V.S. Anil Kumar, M. Marathe, S. Parthasarthy and A. Srinivasan. End-to-End Packet Scheduling in Ad-hoc Radio Networks. Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004:1021-1030.
C. Engelhart, A. Sivasubramaniam, C. Barrett, M. Marathe, J. Smith and M. Morin. A Spatial Analysis of Mobility Models: Application to Wireless Ad Hoc Network Simulation. Proceedings of 37th Annual Simulation Symposium, 2004:25-42.
2003
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.
S. Krumke, R. Liu, E. Lloyd, M. Marathe, R. Ramanathan and S. Ravi. Topology Control Problems Under Symmetric and Asymmetric Thresholds. Proceedings of International Conference on Ad Hoc and Wireless Networks (ADHOC-NOW’03), Lecture Notes in CS, Vol 2865, (Edited by S. Pierre, M. Barbeau and E. Kranakis) Montreal, Canada, 2003:187-198.
C. Barrett, S. Eidenbenz, L. Kroc, M. Marathe and J. Smith. Parametric Probabilistic Sensor Network Routing. Proceedings on 2nd ACM International Workshop on Wireless Sensor Networks and Applications (WSNA’03), 2003:122-131.
C.L. Barrett, H.B. Hunt, II, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns Predecessor and Permutation Existence Problems for Sequential Dynamical Systems. Proceedings of Discrete Mathematics and Theoretical Computer Science , 2003:69-80. Technical Report No: LA-UR-02-180, Los Alamos National Laboratory.
C. Barrett, M. Drozda, A. Marathe and M. Marathe. Analyzing Interaction Between Network Protocols, Topology and Traffic in Wireless Radio Networks. Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), 2003.
2002
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.
C. Barrett, K. Bisset, R. Jacob, G. Konjevod and M Marathe. An Experimental Analysis of a Routing Algorithm for Realistic Transportation Networks. Proceedings of European Symposium on Algorithms (ESA), 2002.
C. Barrett, C. Engelhart, M. Marathe and A. Sivasubramanium. Analyzing the Short-Term Fairness of IEEE 802.11 in Wireless Multi-hop Radiog Networks. Proceedings of 10th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, (MASCOTS’02),, 2002.
M Marathe. Towards a Predictive Complexity Theory. Proceedings of 29th International Colloquium on Automata Languages and Programming, 2002: 22-31.
VSA Kumar and M Marathe. Improved Results for Stackelberg Scheduling Strategies. Proceedings of the 29th International Colloquium on Automata Languages and Programming, 2002: 776-787.
S. Krumke, M. Marathe, D. Poensgen, S. Ravi and H. Wirth. Budgeted Maximum Graph Coverage. Proceedings of 28th International Workshop on Graph Theoretic Concepts in Computer Science , 2002.
C. Barrett, M. Drozda, A. Marathe and M. Marathe. Characterizing the Interaction Between Routing and MAC Protocols in Ad-hoc Networks., Proceedings of 3rd ACM international Symposium on Mobile Ad Hoc Networking and Computing, 2002:92-103.
R. Liu, E. Lloyd, M. Marathe, R. Ramanathan and S. Ravi. Algorithmic Aspects of Topology Control Problems for Ad-hoc Networks. Proceedings of 3rd ACM International Symposium on Mobile Ad Hoc Network and Computing, 2002: 123-134.
C. Barrett, M. Drozda and M. Marathe. A Comparative Experimental Study of Media Access Protocols for Wireless Radio Networks. Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), 2002:405-411.
C. Barrett, S. Eubank, M. Marathe, H. Mortveit and C. Reidys. Science and Engineering of Large Scale Socio-Technical Simulations. Invited paper in Proceedings of 1st International Conference on Grand Challenges in Simulations, 2002.
2001
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.
H.B. Hunt, III, R. E. Stearns and M.V. Marathe. Complexity and Approximability of Quantified and Stochastic Satisfiability Problems. Proceedings of Workshop on Theory and Applications of Satisfiability testing, to appear as Electronic Notes in Discrete Mathematics (ENDM) . 2001:130-143.
C. L. Barrett, H.B. Hunt, III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns. Analysis Problems for Sequential Dynamical Systems and Communicating State Machines. Proceedings of 26th Mathematical Foundations of Computer Science (MFCS 01). Edited by J. Sgall, A. Pultr and P. Kolman, LNCS, VOL. 2136. 2001:159-172.
H. Hunt, III, R. Stearns, and M. Marathe. Strongly Local Reductions and the Complexity/ Efficient Approximability of Algebra and Optimization on Abstract Algebraic Structures. Proceeding of International conference on Symbolic and Algebraic Computations (ISSAC) 2001.
C.L. Barrett, H.B. Hunt, III, M.V. Marathe, S.S. Ravi, D. J. Rosenkrantz, R.E. Stearns and P. Tosic. Garden of Eden and Fixed Point Configurations in Sequential Dynamical Systems. Proceedings of International Conference on Discrete Model in Combinatorics, Computation and Geometry (DMCCG). 2001:95-110.
G. Istrate, M.V. Marathe, and S.S. Ravi. Adversarial Models in Evolutionary Game Dynamics. Proceedings in 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001:719-720.
C. Barrett, D. Cook, V. Faber, G. Hicks, A. Marathe, M. Marathe, A. Srinivasan, Y. Sussman and H. Thornquist. Experimental Analysis of Algorithms for Bilateral-Contract Clearing Mechanisms Arising in Deregulated Power Industry. Proceedings of 5th Workshop on Algorithmic Engineering (WAE), LNCS 2141, 2001: 171-184.
2000
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.
L.J. Dowell, M. Drozda, B. Henderson, V. Loose, M. Marathe, and D. Roberts. Scalability of ELISIMS: Comprehensive Detailed Simulation of Electric Power Industry. Proceedings of IEEE International Conference on Systems, Man and Cybernetics, (SMC), Nashville, 2000.
S. Doddi, M.V. Marathe, S.S. Ravi, D. Taylor, and P. Widmayer. Approximation algorithms for clustering to minimize the sum of diameters. Proceedings in 7th Scandinavian Workshop on Algorithm Theory, (SWAT), Bergen, Norway, 2000.
M.V. Marathe, L.D. Risenger, and A. Panconesi. Experimental Analysis of a Simple Distributed Edge Coloring Algorithm. Proceedings of 12th ACM Symposium on Parallel Algorithms and Architectures, (SPAA) , Maine, 2000:166-175.
R. Carr, S. Doddi, G. Konjevod, and M.V. Marathe. On the Red-Blue Set Cover Problem. Proceedings of 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000:345-353.
E. Czabarka, G. Konjevod, M.V. Marathe, A.G. Percus and D.C. Torney. Algorithms for Optimizing Production DNA Sequencing. Proceedings of 11th ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2000: 399-408.
1999
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.
F. Bassetti, K. Davis, M.V. Marathe, D.J. Quinlan, and B. Philip. Improving Cache utilization of Linear Relaxation Methods: Theory and Practice. Proceedings of 3rd International Symposium on Computing in Object-oriented Parallel Environments (ISCOPE) , 1999:25-36.
1998
M Marathe, H Hunt III, V Radhakrishnan, R Stearns. Approximation algorithms for PSPACE-hard hierarchically and periodically specified problems. SIAM Journal on Computing, 27(5), 1998:1237-1261.
MV Marathe, R Ravi, R Sundaram, SS Ravi, DJ Rosenkrantz, and HB Hunt III. Bicriteria network design problems. J. Algorithms, 28(1), 1998:142-171.
H.B. Hunt III, M.V. Marathe, V. Radhakrish-nan and R.E. Stearns. The Complexity of Planar Counting Problems. SIAM J. Computing, 27(4), 1998:1142–1167.
S.O. Krumke, M.V. Marathe, H. Noltemeier, R. Ravi and S. Ravi. Approximation Algorithms for Certain Network Improvement Problems. Journal of Combinatorial Optimization, 2, 1998:257-288.
S.O. Krumke, H. Noltemeier, H.U. Drangmeister, M.V. Marathe and S.S. Ravi. Modifying Edges of a Network to Obtain Short Subgraphs. invited paper appears in special issue of Theoretical Computer Science, 203(1), 1998:91-121, containing selected papers presented at the 22nd Workshop in Graph Theoretic Concepts in Computer Science (WG), 2000:91-121.
M.V. Marathe, R. Ravi, R. Sundaram, S.S. Ravi, D.J. Rosenkrantz and H.B. Hunt III. Bicriteria Network Design Problems. Journal of Algorithms, 28(1), 1998:142-171.
H.B. Hunt III,M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns. NC-Approximation Schemes for NP-and PSPACE-hard Problems for Geometric Graphs. Journal of Algorithms, 26(1), 1998:238-274.
R. Ravi, R. Sundaram, M.V. Marathe, S.S. Ravi and D.J. Rosenkrantz. Spanning Trees Short or Small. SIAM J. Discrete Mathematics, 9(2), 1996:178-200.
S.O. Krumke, M.V. Marathe and S.S. Ravi. Approximation Algorithms for Broadcast Scheduling Radio Networks. In 2nd International Workshop on Discrete Algorithms and Methods for Mobile computing and Communications (DIALM). Dallas, Texas. 1998.
C. Barrett, R. Jacob, and M.V. Marathe. Formal Language Constrained Path Problems. Proceedings of 6th Scandinavian Workshop on Algorithmic Theory (SWAT) ,. Stockholm, Sweden LNCS 1432, Springer Verlag. 1998:234-245
R. Jacob, M.V. Marathe and K. Nagel. A Computational Study of Routing Algorithms for Realistic Transportation Networks. Proceedings of 2nd Workshop on Algorithmic Engineering. Saarbrucken, Germany, 1998.
S.O. Krumke, M.V. Marathe, H. Noltemeier, S.S. Ravi, and H.C. Wirth. Upgrading Bottleneck Constrained Forests. Proceedings in 24th Workshop in Graph Theoretic Concepts in Computer Science (WG) . Smolenice-Castle, Slovakia, 1517 LNCS, Springer, 1998:215-226.
M.V. Marathe, H.B. Hunt, III, D.J. Rosenkrantz and R.E. Stearns. Theory of Periodically Specified Problems: Complexity and Approximability. Proceedings of 13th IEEE Conference on Computational Complexity, Buffalo, NY, 1998.
D. Cook, V. Faber, M Marathe, A. Srinivasan and Y. Sussmann. Low-Bandwidth Routing and Electrical Power Networks. Proceedings of 25th International Colloquium on Automata, Languages and Programming (ICALP), 1998:604-615.
1997
S.O. Krumke, H. Noltemeier, S.S. Ravi and M.V. Marathe. Compact Location Problems with Budget and Communication Constraints. Theoretical Computer Science, 181(2), 1997:379-404.
M.V. Marathe, V. Radhakrishnan, H.B. Hunt, III and S.S. Ravi. Hierarchically Specified Unit Disk Graphs. Theoretical Computer Science, 174(1-2), 1997:23-65.
S.O. Krumke, M.V. Marathe, H. Noltemeier, R. Ravi, S.S. Ravi, R. Sundaram, and H.C. Wirth. Improving Spanning Trees by Upgrading Nodes. Proceedings of 24th International Colloquium on Automata, Languages and Programming (ICALP) . Bologna, Italy, LNCS Vol. 1256, Springer Verlag, 1997:281-29.
S. Doddi, M.V. Marathe, A. Mirzaian, B. Moret, and B. Zhu. Map Labeling Problems. Proceedings of 8th ACM-SIAM Symposium on Discrete Algorithms (SODA) . San Francisco, CA, 1997:148-157.
1996
M.V. Marathe, R. Ravi and R. Sundaram. Service Constrained Network Design Problems. invited paper appears in a special issue of Nordic Journal of Computing , 3(4) 1996:367-387, containing selected presented at the 5th Scandinavian Workshop on Algorithm Theory (SWAT).
M.V. Marathe and S.S. Ravi Approximation Algorithms for the Minimum Satisfiability Problem. Information Processing Letters, (IPL), , 58(1) 1996:23-29.
M.V. Marathe, H.B. Hunt III and S.S. Ravi. Approximation Algorithms for Domatic Partition and On-line Coloring of Circular Arc Graphs. Discrete Applied Mathematics, 64 (2), 1996:135-149.
S.R. Arikati, A. Dessmark, A. Lingas, and M.V. Marathe. Approximation Algorithms for Maximum Two-Dimensional Pattern Matching. Proceedings of 7th Annual Symposium on Combinatorial Pattern Matching (CPM) . Laguna Beach, California, LNCS 1075, Springer Verlag. 1996:348-360
S.O. Krumke, H. Noltemeier, H.U. Drangmeister, M.V. Marathe, and S.S. Ravi. Modifying Edges of a Network to Obtain Short Subgraphs. Proceedings of 22nd Workshop in Graph Theoretic Concepts in Computer Science (WG) . Italy, 1996:91-121.
M.V. Marathe, R. Ravi, and R. Sundaram. Service Constrained Network Design Problems. In 5th Scandinavian Workshop on Algorithm Theory (SWAT) . Reykjavik, Iceland, LNCS1097, Springer Verlag, 1996:28-40.
1995
M.V. Marathe, H. Breu, H.B. Hunt,III, S.S. Ravi and D.J. Rosenkrantz. Simple Heuristics for Unit Disk Graphs. Networks, 25, 1995:59-68.
S.O. Krumke, H. Noltemeier, S.S. Ravi, and M.V. Marathe. Compact Location Problems with Budget and Communication Constraints. In 1st International Conference on Computing and Combinatorics. X’ian, China, LNCS Volume 959, Springer Verlag. Invited for presentation at Computing and Combinatorics 95, Brest, France, 1995:510-519.
M. V. Marathe, R. Ravi, R. Sundaram, S.S. Ravi, D.J. Rosenkrantz, and H.B. Hunt, III. Bicriteria Network Design Problems. Proceedings of 22nd International Colloquium on Automata, Languages and Programming (ICALP) . Szeged, Hungary, LNCS 944, Springer Verlag, 1995:487-498.
S.O. Krumke, H. Noltemeier, S.S. Ravi, and M.V. Marathe. Complexity and Approximability of Certain Bicriteria Location Problems. In 21st Workshop in Graph Theoretic Concepts in Computer Science (WG). Aachen, Germany, LNCS Volume 1017. Also invited for presentation at 8th Meeting of the EURO Working Group on Locational Analysis (EWGLA8) . Lambrecht, Germany, 1995:73-87
1994
M.V. Marathe, H.B. Hunt, III and S.S. Ravi. The Complexity of Approximating PSPACE-Complete Problems for Hierarchical Specifications. invited paper appears in a special issue of Nordic Journal of Computing, 1 (3) 1994:275-316, containing selected papers presented at the 20th International Colloquium on Automata, Languages and Programming (ICALP).
H.B. Hunt, III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz, and R.E. Stearns. Parallel Approximation Schemes for a Class of Planar and Near Planar Combinatorial Problems. Proceedings of 14th Foundations of Software Technology and Theoretical Computer Science (FST &TCS), LNCS 761, Springer Verlag. 1994:342-353.
M.V. Marathe, H.B. Hunt, III, R.E. Stearns, and V. Radhakrishnan. Approximation Schemes for PSPACE-Complete Problems for Succinct Specifications. Proceedings of 26th Annual ACM Symposium on the Theory of Computing (STOC) . Montreal, Canada, 1994:468-478.
H.B. Hunt, III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns. A Unified Approach to Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs. Proceedings of 2nd Annual European Symposium on Algorithms, (ESA) . LNCS 855, Springer Verlag, 1994:468-477.
H.B. Hunt, III, M.V. Marathe, and R.E. Stearns. Generalized CNF Satisfiability Problems and Non-Efficient Approximability. Proceedings of 9th IEEE Annual Conference on Structure in Complexity Theory (Structures) , 1994:355-366.
1993
R. Ravi; M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, and H.B. Hunt, III. Many Birds with One Stone: Multi-Objective Approximation Algorithms. Proceedings of 25th Annual ACM Symposium on the Theory of Computing (STOC), 1993:438-447.
M.V. Marathe, H.B. Hunt, III, and S.S. Ravi. The Complexity of Approximating PSPACE-Complete Problems for Hierarchical Specifications. Proceedings of 20th International Colloquium on Automata, Languages and Programming (ICALP) . LNCS 7700, Springer Verlag, 1993:76-87.
V. Radhakrishnan, S.O. Krumke, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz. Compact Location Problems. Proceedings of 13th Foundations of Software Technology and Theoretical Computer Science (FST & TCS) . LNCS 761, Springer Verlag, 1993:238-247.
M.V. Marathe, H.B. Hunt, III and S.S. Ravi. Approximation Algorithms for On-line Coloring and Domatic Partition of Circular Arc Graphs. Proceedings of 5th International Conference on Computing and Information (ICCI) , 1993:26-30
M.V. Marathe, V. Radhakrishnan, H.B. Hunt, III and S.S. Ravi. Hierarchically Specified Unit Disk Graphs. Proceedings of 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG) . LNCS 790, Springer Verlag, 1993:21-32.
1992
R. Ravi, M.V. Marathe and C. PanduRangan. An Optimal Algorithm to Solve the All-Pair Shortest Path Problem on Interval Graphs. Networks, 39, 1992:87-93.
M.V. Marathe, R. Ravi and C. PanduRangan. Generalized Vertex Covering in Interval Graphs. Discrete Applied Mathematics, 39(1) 1992:87-93.
M.V. Marathe, H. Breu, H.B. Hunt, III, S.S. Ravi and D.J. Rosenkrantz. Simple Heuristics for Unit Disk Graphs. Proceedings of 4th Canadian Conference on Computational Geometry (CCCG) , 1992:244-249.

(Last updated: Tues Sept 15 12:09:05 EST 2009)

Madhav V. Marathe

Professional Preparation

Research Interests

Awards

Professional Activities

Selected Case Studies

Selected Presentations

Selected Publications

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

1998

1997

1996

1995

1994

1993

1992