Research: Sriram Pemmaraju

Research

My research interests are in combinatorics and graph theory, combinatorial optimization, approximation algorithms, and distributed algorithms. Over the last few years, I have focused on three specific subareas:

Approximation algorithms for graph coloring problems that arise in scheduling applications. These include problems such as max-coloring, interval coloring, etc. Much of this is joint work with my colleague Kasturi Varadarajan and my student Rajiv Raman.
Bounds on the chromatic number for graph coloring with additional constraints (for example, equitable coloring). Some of this is joint work with Alexandr Kostochka.
Distributed approximation algorithms for combinatorial optimization problems that arise in wireless adhoc networks. These include problems such as topology control, construction of sparse light-weight spanners, domatic partition, etc. Some of this is with colleagues Sukumar Ghosh and Ted Herman and students Kevin Lillis, Saurav Pandit, and Imran Pirwani.

Motivated by Bruno Codenotti and Kasturi Varadarajan, I have also dabbled in algorithms for computing market equilibria for certain types of markets. Between 2000 and 2003, along with Steven Skiena, I spent a significant amount of my time rewriting the Combinatorica package and the Combinatorica book. Before that I have worked on self-stabilization and with Lenny Heath, on graph layouts.

Ph.D. STUDENTS:

Arobindo Gupta: graduated 1997, dissertation Fault-containing self-stabilizing algorithms, Associate Professor, IIT Kharagpur.
Mirela Damian-Iordache: graduated 2000, Assistant Professor, Villanova University.
Rajiv Raman: current, dissertation topic Approximation algorithms for max-coloring.
Kevin Lillis: current, dissertation topic Robust topology control and routing in wireless ad-hoc networks.
Saurav Pandit: current. Saurav is exploring the topic: Distributed Approximation Algorithms.
Imran Pirwani: current, dissertation topic Scheduling in wireless ad-hoc networks.

THE COMBINATORICA BOOK:

SOME PAPERS:

If you want an electronic version of any the papers below send me e-mail at sriram@cs.uiowa.edu.

``The Randomized Coloring Procedure with Symmetry-Breaking,'' with Aravind Srinivasan. ICALP, 2008. postscript and pdf.
``On the Efficiency of a Local Iterative Algorithm to Compute Delaunay Realizations,'' with Kevin Lillis. WEA, 2008. pdf.
``Temporal Partition in Sensor Networks,'' with Ted Herman, Laurence Pilard, and Morton Mjelde. SSSS, 2007. postscript and pdf.
``Topology Control and Geographic Routing in Realistic Wireless Networks,'' with Kevin M. Lillis and Imran A. Pirwani. ADHOC-NOW, 2007. postscript and pdf.
``Good Quality Virtual Realization of Unit Ball Graphs,'' with Imran A. Pirwani. ESA, 2007. postscript and pdf.
``Distributed Spanner Construction in Doubling Metric Spaces,'' with Mirela Damian and Saurav Pandit. OPODIS, 2006. postscript and pdf.
``Local Approximation Schemes for Topology Control,'' with Mirela Damian and Saurav Pandit. PODC, 2006. postscript and pdf.
``Energy Conservation in Wireless Sensor Networks via Domatic Partitions,'' with Imran Pirwani. MOBIHOC, 2006. postscript and pdf.
``Oriented Edge Colorings and Link Scheduling in Sensor Networks,'' with Ted Herman and Imran Pirwani. SENSORWARE, 2006. postscript and pdf.
``APX-hardness of Domination Problems in Circle Graphs,'' with Mirela Damian. Information Processing Letters, 97(6), 231-237, 2006. postscript and pdf.
``Topology Control with Limited Geometric Information,'' with Kevin Lillis. OPODIS 2005. postscript and pdf.
``Approximation Algorithms for the Max-Coloring Problem,'' with Rajiv Raman. ICALP 2005. postscript and pdf.
``An experimental study of different approaches to solve the market equilibrium problem,'' with Bruno Codenotti, Benton Mccune, Rajiv Raman, and Kasturi Varadarajan. ALENEX 2005.
``Coloring d-degenerate graphs equitably'', with Alexander Kostochka, Kittikorn Nakprasit. SIAM Journal on Discrete Math, Volume 19, Number 1, 2005. postscript and pdf.
``On the Polynomial Time Computation of Equilibria for Certain Exchange Economies,'' with Bruno Codenotti and Kasturi Varadarajan. SODA 2005.
``Algorithms Column: The Computation of Market Equilibria,'' with Bruno Codenotti and Kasturi Varadarajan. SIGACT News, Volume 35(4), December 2004, 23-37.
``Robust Topology Control Protocols,'' with Sukumar Ghosh, Kevin Lillis, and Saurav Pandit. OPODIS 2004. postscript and pdf.
``Approximating Interval Coloring and Max-Coloring in Chordal Graphs,'' with Sriram Penumatcha and Rajiv Raman. 3rd International Workshop on Efficient and Experimental Algorithms 2004, (WEA 2004), Lecture Notes in Computer Science 3059, Editors C.C. Ribeiro and S.L. Martins. postscript and pdf.
``Computing Optimal Diameter-Bounded Polygon Partitions,'' with Mirela Damian. Algorithmica, 2004, (40), 1-14. postscript and pdf.
``Buffer Minimization Using Max-Coloring,'' with Rajiv Raman and Kasturi Varadarajan. Proceedings of the Fifteenth ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004. postscript and pdf.
``Processor-Efficient Sparse Matrix-Vector Multiplication,'' with Lenwood S. Heath and Calvin J. Ribbens. Computers and Mathematics with Applications, 48 (2004), 589-608. postscript and pdf.
``Equitable Colorings with Constant Number of Colors,'' with Kittikorn Nakprasit and Alexandr Kostochka. Proceedings of the Fourteenth ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003.
``Fault-containing self-stabilizing distributed protocols,'' with Sukumar Ghosh, Arobinda Gupta, and Ted Herman. To appear in a special issue on Self-Stabilization of Distributed Computing, 2002.
``A $(2+\epsilon)$ -approximation scheme for minimum domination on circle graphs,'' with Mirela Damian-Iordache. Journal of Algorithms, 42(2), 255-276, 2002.
``Equitable coloring extends Chernoff-Hoeffding bounds,'' Proceedings of the 5th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2001), Berkeley, California, 285-296, August 2001.
``Equitable colorings extend Chernoff-Hoeffding bounds,'' (short paper) Proceedings of the 12th Annual SIAM-ACM Symposium on Discrete Algorithms (SODA 2001), Washington DC, January 2001.
``Computing optimal $\alpha$ -Fat and $\alpha$ -small decompositions,'' (short paper) with Mirela Damian-Iordache. Proceedings of the 12th Annual SIAM-ACM Symposium on Discrete Algorithms (SODA 2001), Washington DC, January 2001.
``A (2+ $\epsilon$ )-approximation scheme for minimum domination on circle graphs,'' with Mirela Damian-Iordache. Proceedings of the 11th Annual SIAM-ACM Symposium on Discrete Algorithms (SODA 2000), San Francisco, January 2000.
``Error-detecting codes and fault-containing self-stabilization,'' with Ted Herman, Information Processing Letters, 73(1-2): pp. 41-46, 2000.`
``Hardness of approximating independent domination in circle graphs,'' with Mirela Damian-Iordache. Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC 99), Chennai, India, December 1999.
``Constant-factor approximation algorithms for domination problems on circle graphs,'' with Mirela Damian-Iordache. Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC 99), Chennai, India, December 1999.
``Self-Stabilizing algorithms for finding centers and medians of trees,'' with Steven C. Bruell, Sukumar Ghosh, and Mehmet Hakan Karaata. SIAM Journal on Computing, Vol. 29, No. 2, pp. 600-614, 1999.
``Stack and queue layouts of dags - Part II,'' with Lenwood S. Heath. SIAM Journal on Computing, Vol. 28, No. 5, pp. 1588-1626, 1999.
``Stack and queue Layouts of dags - Part I,'' with Lenwood S. Heath and Ann Trenk. SIAM Journal on Computing, Vol. 28, No. 4, pp. 1510-1539, 1999.
``Stack and queue layouts of posets'' with Lenwood S. Heath. SIAM Journal on Discrete Mathematics, Vol. 10, No. 4, pp. 599-625, 1997.
``A self-stabilizing algorithm for the maximum flow problem,'' with Sukumar Ghosh and Arobinda Gupta. Distributed Computing, Vol. 10, pp. 167-180, 1997.
``Using graph coloring in an algebraic compiler,'' with Teodor Rus. Acta Informatica, Vol. 34, Fasc. 3, 1997.
``Automatic data decomposition for message-passing machines,'' with Mirela Damian-Iordache. Proceedings of the 10th International Workshop on Languages and Compilers for Parallel Computing (LCPC 97), Minneapolis, August 1997.
``Trade-offs in fault-containing self-stabilization,'' (Abstract) with Sukumar Ghosh. Proceedings of Sixteenth ACM Symposium on Principles of Distributed Computing (PODC 97), Santa Barbara, August 1997.
``Trade-offs in fault-containing self-stabilization,'' with Sukumar Ghosh. Proceedings of the Third Workshop on Self-Stabilizing Systems (WSSS 97), Santa Barbara, August 1997.
``Fault-containing network protocols,'' with Sukumar Ghosh and Arobinda Gupta. presented at Twelfth ACM Symposium on Applied Computing: Parallel and Distributed Computing Track, San Jose, February 1997.
``A fault-containing self-stabilizing algorithm for spanning trees,'' with Sukumar Ghosh and Arobinda Gupta. Journal of Computing and Information, Vol. 2, No. 1, pp. 322-338, 1996.
``A fault-containing self-stabilizing algorithm for spanning trees,'' with Sukumar Ghosh and Arobinda Gupta. Eighth International Conference of Computing and Information, Waterloo, Ontario, Canada, June 1996.
``Fault-containing self-stabilizing algorithms,'' with Sukumar Ghosh, Arobinda Gupta, and Ted Herman. Fifteenth ACM Symposium on Principles of Distributed Computing (PODC 96), Philadelphia, May 1996, pp. 45-54.
``Recognizing leveled-planar dags in linear time,'' Lenwood S. Heath and Sriram V. Pemmaraju. Proceedings of Graph Drawing 1995 (GD 95), pp. 300-311.
``Self-stabilizing dynamic programming algorithms on trees,'' with Sukumar Ghosh, Arobinda Gupta, and Mehmet Hakan Karaata. Proceedings of the Second Workshop on Self-Stabilizing Systems (WSSS 95), Las Vegas, May 1995, pp. 11.1-11.15.
``A Self-stabilizing algorithm for the maximum flow problem,'' with Sukumar Ghosh and Arobinda Gupta. Proceedings of the International Phoenix Conference on Computers and Communication, Phoenix, March 1995, pp. 8-14.
``New results for the minimum weight triangulation problem,'' with Lenwood S. Heath. Algorithmica, 12, 533-552, 1994.
``Self-stabilizing algorithms for finding centers and medians of trees,'' (Abstract) with Steven C. Bruell, Sukumar Ghosh, and Mehmet Hakan Karaata. Proceedings of the ACM Annual Symposium on Principles of Distributed Computing (PODC 94), Los Angeles, May 1994, pp. 374.
``Worst case analysis of PR quadtree space utilization,'' with Clifford A. Shaffer. Information Processing Letters, 49, 263-267, 1994.
``Stack and queue layouts of directed acyclic graphs'' (extended abstract) with Lenwood S. Heath and Ann Trenk. Proceedings of the DIMACS Workshop on Planar Graphs: Structure and Algorithms, William T. Trotter, editor, American Mathematical Society, Providence, Rhode Island, 1993, pp. 5-11.

PAPERS IN UNREFEREED CONFERENCES

``Equitable colorings lead to generalized Chernoff-Hoeffding bounds,'' Tenth SIAM Conference on Discrete Mathematics, Minneapolis, June, 2000.
``Self-stabilizing distributed algorithms,'' National Workshop on Distributed Computing, Calcutta, India, January 1998.
``Stack and queue layouts of posets,'' with Lenwood S. Heath. Minisymposium on Stack and Queue Layouts of Directed Graphs at Seventh SIAM Conference on Discrete Mathematics, Albuquerque, New Mexico, June 22, 1994.
``Using staircase covers for matrix-vector multiplication,'' with Lenwood S. Heath and Calvin J. Ribbens, Seventh SIAM Conference on Discrete Mathematics, Albuquerque, New Mexico, June 22, 1994.
``Stack and queue layouts of directed acyclic graphs,'' with Lenwood S. Heath. Twenty-Third Southeastern International Conference on Combinatorics, Graph theory and Computing, Boca Raton, Florida, February, 1992.
``Improved algorithms for the minimum weight triangulation problem,'' with Lenwood S. Heath. Fifth SIAM Conference on Discrete Mathematics, Atlanta, Georgia, June 11, 1990.