Publications (partial list)

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

Network/Packet Classifier Optimization

• Topological Transformation Approaches to Optimizing TCAM-based Packet Classification Systems
  • Local copy. The definitive version is available following the link above.
  • coauthors: Chad Meiners and Alex Liu
  • Proceedings of the joint ACM SIGMETRICS IFIP Performance , pages 73-84, 2009.

• Optimization Based Rate Allocation and Scheduling in TDMA Based Wireless Mesh Networks
  • Local copy. The definitive version is available by following the link above.
  • coauthors: Bo Wang and Matt Mutka
  • Proceedings of IEEE International Conference on Network Protocols (ICNP), pages 147-156, 2008.

• Firewall Compressor: An Algorithm for Minimizing Firewall Policies
  • Local copy. The definitive version is available following the link above.
  • coauthors: Chad Meiners and Alex Liu
  • Proceedings of IEEE Conference on Computer Communications (INFOCOM), 2008.

• TCAM Razor: A Systematic Approach Towards Minimizing Packet Classifiers in TCAM's
  • Local copy. The definitive version is available following the link above.
  • coauthors: Chad Meiners and Alex Liu
  • Proceedings of IEEE International Conference on Network Protocols (ICNP), pages 266-275, 2007.

On-line Algorithms and Scheduling Papers

• SRPT Optimally Uses Faster Machines to Minimize Flow Time
  • Local copy. The definitive version is available at the ACM digital library following the link above.
  • coauthor: Jason McCullough
  • ACM Transactions on Algorithms (TALG), Volume 5, Issue 1, Article Number 1, 2008.
  • Preliminary version appeared in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 350-358, 2004.

• List's worst-average-case or WAC ratio
  • Local copy. The definitive version is available following the link above.
  • coauthor: Christopher J Osborn
  • Journal of Scheduling, 11(3), pages 213-215, 2008.
  • Published online in 2007.

• Mixed Criteria Packet Scheduling
  • Local copy. The definitive is available following the above link.
  • coauthor: Chad Meiners
  • Proceedings of Algorithmic Aspects of Information Management, 2007, pages 120-133, Lecture Notes in Computer Science 4508, Springer.

• Greedy Multiprocessor Server Scheduling
  • Local copy. The definitive version is available following the link above.
  • coauthor: Carl Bussema
  • Operations Research Letters, 34(4), pages 451-458, 2006.

• Online Scheduling
  • coauthors: Kirk Pruhs and Jiri Sgall
  • in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Joseph Leung (editor), Chapter 15, CRC Press, 2004.

• Optimal Replacement is NP-Hard for Non-Standard Caches
  • Local copy. The definitive version is available at the IEEE web site following the link above.
  • coauthors: Mark Brehob, Richard Enbody, and Stephen Wagner
  • IEEE Transactions on Computers, 53 (1), 73-76, 2004.

• On-line Restricted Caching
  • Local copy. The definitive version is available at www.springerlink.com; follow the link above.
  • coauthors: Mark Brehob, Richard Enbody, and Stephen Wagner
  • Journal of Scheduling, 6, pages 149-166, 2003.
  • Preliminary version appeared in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 374-383, 2001.

• Existence Theorems, Lower Bounds and Algorithms for Scheduling to Meet Two Objectives
  • Local copy. The definitive version is available by follwoing the link above.
  • coauthors: April Rasala, Cliff Stein, and Patchrawat Uthaisombut
  • Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 723-731, 2002.

• Optimal Time-Critical Scheduling Via Resource Augmentation
  • Local copy. The definitive version can be found at www.springer.com by following the above link.
  • coauthors: Cynthia A. Phillips, Cliff Stein, and Joel Wein
  • Algorithmica, 32, pages 163-200, 2002.
  • Preliminary version appeared in Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), 1997.

• The k-client Problem
  • Local copy. The definitive version can be found at Elseveier Science's web cite at www.sciencedirect.com following the link above.
  • coauthors: Houman Alborzi, Patchrawat Uthaisombut, and Stephen Wagner
  • Journal of Algorithms, 41, pages 115-173, 2001.
  • Preliminary version appeared in Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1997.

• Errata: A New Algorithm for Scheduling Periodic, Real-Time Tasks
  • Local copy. The definitive version can be found by following the link above.
  • coauthors: Bala Kalyanasundaram and Kirk Pruhs
  • Algorithmica, 28, pages 269-270, 2000.

• Generating Adversaries for Request-Answer Games
  • Local copy. The definitive version can be found at the ACM digital library by following the above link.
  • coauthors: Todd Gormley, Nicholas Reingold, and Jeffery Westbrook
  • Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 564-565, 2000.

• Applying Extra Resource Analysis to Load Balancing
  • Local copy. The definitive version can be found at the Wiley interscience site by following the above link.
  • coauthors: Mark Brehob and Patchrawat Uthaisombut
  • Journal of Scheduling, 3, pages 273-288, 2000.
  • Preliminary version appeared in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

• A tight lower bound for the best-Alpha algorithm
  • Local copy. The definitive version can be found at Elseveier Science's web cite at www.sciencedirect.com following the link above.
  • coauthor: Patchrawat Uthaisombut
  • Information Processing Letters, 71, pages 17-22, 1999.
  • Preliminary version appeared in ACM-SIAM SODA 1999 as "Lower bounds for SRPT-subsequence algorithms for nonpreemptive scheduling"

• On-line Scheduling with Lookahead: Multipass Assembly Line Machines
  • coauthors: Rajeev Motwani and Vijay Saraswat
  • INFORMS Journal on Computing, Volume 10, Number 3, pages 331-340, Summer 1998.

• A Unified Analysis of Paging and Caching
  • Local copy. The definitive version can be found at www.springerlink.com by following the above link.
  • Eric Torng
  • Algorithmica, Volume 20, pages 175-200, 1998.
  • Preliminary version appeared in IEEE FOCS 1995.

• A Better Algorithm for an Ancient Scheduling Problem
  • Local copy. The definitive version can be found at Elseveier Science's web cite at www.sciencedirect.com following the link above.
  • coauthors: David Karger and Steven Phillips
  • Journal of Algorithms, Volume 20, pages 400-430, 1996.
  • Preliminary version appeared in ACM-SIAM SODA, 1994.

• Non-clairvoyant Scheduling
  • Local copy. The definitive version can be found at Elseveier Science's web cite at www.sciencedirect.com following the link above.
  • coauthors: Rajeev Motwani and Steven Phillips
  • Theoretical Computer Science, Volume 130, pages 17-47, 1994.
  • Preliminary version appeared in ACM-SIAM SODA, 1993.

• Non-omniscient Scheduling
  • Eric Torng
  • Stanford University PhD Thesis, July, 1994

• `Signature Sets', Minimal Fragment Sets for Identifying Protein Disulfide Structures with Cyanylation-Based Mass Mapping Methodology
  • Local copy. The definitive version is available by following the link above.
  • coauthors: Wei Wu, Wei Huang, Jianfeng Qi, Yi-Te Chou, and J. Throck Watson
  • Journal of Proteome Research, 3 (4), pages 770-777, 2004.

• Algorithm-Assisted Elucidation of Disulfide Structures: Application of the Negative Signature Mass Algorithm to Mass-Mapping the Disulfide Structure of the 12-Cysteine Transforming Growth Factor B Type II Receptor Extracellular Domain
  • Local copy. The definitive version is available by following the link above.
  • coauthors: Chad Borges, Jianfeng Qi, Wei Wu, Andrew Hinck, and J. Throck Watson
  • Analytical Biochemistry, 329 (1), pages 91-103, 2004.

• Automated Data Interpretation Based on the Concept of Negative Signature Mass for Mass-Mapping Disulfide Structures of Cystinyl Proteins
  • Local copy. The definitive version is available by following the link above.
  • coauthors: Jianfeng Qi, Dehua Hang, Matthew Rupp, Chad Borges, Wei Wu, and J. Throck Watson
  • Journal of the American Society for Mass Spectrometry (JASMS), 14(9), pages 1032-1038, 2003.
  • Article selected for inclusion in Proteomics Select, a virtual journal of proteomics designed to bring together select journal papers published by Elsevier Science and Academic Press focused on the emerging field of proteomics.

• On the Gradual Evolution of Complexity and the Sudden Emergence of Complex Features Organisms
  • coauthors: Wei Huang and Charles Ofria
  • Artificial Life , 14(3), pp. 255-263, 2008

• The effect of natural selection on the performance of maximum parsimony
  • Local copy.
  • coauthors: Dehuah Hang, Charles Ofria, and Thomas M. Schmidt
  • Biomed Central Evolutionary Biology, 7:94, 2007

• The Evolution of Structural Organization in Digital Organisms
  • coauthors: Matthew Rupp and Charles Ofria
  • Proceedings of the Tenth International Conference on the Simulation and Synthesis of Living Systems (ALIFE X), pp. 268-274, 2006

• Measuring Biological Complexity in Digital Organisms
  • coauthors: Wei Huang and Charles Ofria
  • Proceedings of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9), pp. 315-321, 2004

• Using Avida to Test the Effects of Natural Selection on Phylogenetic Reconstruction Methods
  • coauthors: George I. Hagstrom, Dehua Hang, and Charles Ofria
  • Artificial Life, 10, pages 157-166, 2004

• The Effect of Natural Selection on Phylogeny Reconstruction Algorithms
  • Local copy.
  • coauthors: Dehua Hang, Charles Ofria, and Thomas Schmidt
  • In Proceedings of Genetic and Evolutionary Computation (GECCO), pages 13-24, 2003

• Source Limited Inclusive Routing: A New Paradigm for Multicast Communication
  • Local copy. The definitive version can be found at the Wiley interscience site by following the above link.
  • coauthors: Barbara D. Birchler and Abdol-Hossein Esfahanian
  • Networks, Volume 35, Number 1, pages 40-55, 2000.
• Sufficient Conditions for Optimal Multicast Communication
  • Local copy. The definitive version can be found at the IEEE digital library by following the above link.
  • coauthors: Barbara D. Birchler and Abdol-Hossein Esfahanian
  • Proceedings of the International Conference on Parallel Processing, pages 390-393, 1997.

• Information Dissemination in Restricted Routing Networks
  • coauthors: Barbara D. Birchler and Abdol-Hossein Esfahanian
  • Proceedings of the International Symposium on Combinatorics and Applications, pages 33-44, 1996.

• Toward a General Theory of Unicast-Based Multicast Communication
  • coauthors: Barbara Birchler and Abdol-Hossein Esfahanian
  • Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Volume 1017, pages 237-251, Springer-Verlag, 1995

Other Topics

• A framework for developing ecosystem-specific nutrient criteria: Integrating biological thresholds with predictive modeling (scroll down to find article)
  • Local copy. The definitive version can be found at the ASLO site by following the above link.
  • coauthors: Patricia A Soranno, Kendra Spence Cheruvelil, R. Jan Stevenson, Scott L. Rollins, Sarah W. Holden, and Sylvia Heaton
  • Limnology and Oceanography, Volume 52, Number 2, pages 773-787, 2008.

• Inferring Relatedness of a Macromolecule to a Sequence Database Without Sequencing
  • coauthors: Jin Kim, James R. Cole, and Sakti Pramanik
  • Proceedings of Intelligent Systems for Molecular Biology, pages 125-133, 1996.

• A Novel Fault Tolerance Technique for Recursive Least Squares Minimization
  • coauthors: Cynthia J. Anfinson and Franklin T. Luk
  • Journal of VLSI Signal Processing, 1, pages 181-188, 1989
  • Preliminary version appeared in Advanced Algorithms and Architectures for Signal Processing III, Proceedings SPIE Vol. 975, pages 268-276, 1988
  • currently not on-line

• Fault Tolerance Techniques for Systolic Arrays
  • coauthor: Franklin T. Luk
  • Real Time Signal Processing X, Proceedings SPIE Vol. 827, pages 30-36, 1987
  • currently not on-line