Experimental Algorithmics: Projects

Main Page
Research Projects
Relevant Links
Computer Science
  • In collaboration with the Center for Computational Biology and Bioinformatics and, in particular, its codirector, Tandy Warnow, at the University of Texas, I am working on several projects in computational biology -- all involving phylogeny reconstruction: given molecular or gene data about a collection of organisms and a model of evolution, construct the evolutionary tree for these organisms that most closely fits the model. This is an extremely difficult computational problem, complicated by a number of biological considerations. Many algorithms have been designed by biologists and computer scientists, but few have been rigorously analyzed and compared. Moreover, most of the work has been done for molecular data (DNA sequences or amino-acid sequences), with little done so far on the emerging whole-genome approach, where each organism is described by its gene sequence(s). We are working with both types of data, conducting very large experiments (the current set has been running for over 10 weeks on 40 computers...), attempting to harness parallel computing, and also designing new algorithms. We have a large collection of papers on the topic -- see my list of papers from the front page. This project is supported at UNM by three separate grants from the National Science Foundation, EIA-01-21377, EIA 01-13095, and DEB-01-20709.
  • Under grant ITR 00-81404 from the National Science Foundation, I am working with David Bader on developing efficient parallel algorithms for shared-memory machines (such as SMPs). The grant supports 3 graduate research assistants and 2 undergraduate researchers; other research assistants participate under other sources of funding. The research was greatly assisted by a grant from Sun Microsystems, combined with money from the Department of Computer Science's NSF Infrastructure grant EIA 95-03064, that allowed us to acquire a 14-processor, 14GB, shared-memory Sun Enterprise E4500, which has been our main research platform ever since.
    E4500 photo
  • I collaborate with Madhav Marathe of Los Alamos Laboratories on various approximation problems in computational geometry. One problem is automatic map labeling: given point, line, and area features, how can the largest possible labels be placed so as not to obscure the features and observe some basic aesthetic criteria? In a recent SODA paper, our PhD student Srinivas Doddi and we presented provably good heuristics, both in the worst-case and in a randomized setting. Our approaches rely on the solution of k-nearest-neighbor problems in the plane. (An implementation is under way, thanks to one of my MS students, Jim Tanzola.) Another problem arises from mobile computing: partition and allocation problems among nodes and edges of a connectivity graph. Preliminary results indicate that provably good heuristics are also possible for this problem.
  • As part of my work as Editor-in-Chief of the ACM Journal of Experimental Algorithms, I am working with the ACM and with colleagues around the world in developing mechanisms for sharing data, instance generators, code, etc. Since the JEA is also ACM's first on-line journal, developing its mechanisms has been another task, which is reviewed in a recent article in the Journal of Electronic Publishing.