| 1999 | I/O-Complexity of Graph Algorithms. | Kamesh Munagala, Abhiram G. Ranade |
| 1999 | Combinatorics Helps for Hexahedral Mesh Generation in CAD. | Matthias Mller-Hannemann |
| 1999 | Dual-Issue Scheduling with Spills for Binary Trees. | Waleed Meleis, Edward S. Davidson |
| 1999 | Compass Permits Leader Election. | Jacques Mazoyer, Codrin M. Nichitiu, Eric Rmila |
| 1999 | Approximation Algorithms for Protein Folding Prediction. | Giancarlo Mauri, Giulio Pavesi, Antonio Piccolboni |
| 1999 | On the Optimality of Parsing in Dynamic Dictionary Based Data Compression. | Yossi Matias, Sleyman Cenk Sahinalp |
| 1999 | An Analysis of the Burrows-Wheeler Transform. | Giovanni Manzini |
| 1999 | A Deterministic Approximation Algorithm for a Minmax Integer Programming Problem. | Chi-Jen Lu |
| 1999 | An Algorithm to Symbolically Describe Flows on Surfaces. | Luis-Miguel Lopez, Philippe Narbel |
| 1999 | The Advantages of Forward Thinking in Generating Rooted and Free Trees. | Gang Li, Frank Ruskey |
| 1999 | Empirical Investigation of the Markov Reference Model. | Vincenzo Liberatore |
| 1999 | New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. | Frank Thomson Leighton, Satish Rao, Aravind Srinivasan |
| 1999 | Distinguishing String Selection Problems. | J. Kevin Lanctt, Ming Li, Bin Ma, Shaojiu Wang, Louxin Zhang |
| 1999 | Trade-offs Between Speed and Processor in Hard-Deadline Scheduling. | Tak Wah Lam, Kar-Keung To |
| 1999 | Cache Performance Analysis of Traversals and Random Accesses. | Richard E. Ladner, James D. Fix, Anthony LaMarca |
| 1999 | Roundness Estimation via Random Sampling. | Ravi Kumar, D. Sivakumar |
| 1999 | Indexing Schemes for Random Points. | Elias Koutsoupias, David Scot Taylor |
| 1999 | Placement Algorithms for Hierarchical Cooperative Caching. | Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman |
| 1999 | Online Resource Minimization. | Anton J. Kleywegt, Vijay S. Nori, Martin W. P. Savelsbergh, Craig A. Tovey |
| 1999 | Wavelength Conversion in Optical Networks. | Jon M. Kleinberg, Amit Kumar |
| 1999 | Interleaved Prefetching. | Tracy Kimbrel |
| 1999 | A Uniform Framework for Approximating Weighted Connectivity Problems. | Samir Khuller, Balaji Raghavachari, An Zhu |
| 1999 | The Data Broadcast Problem with Non-Uniform Transmission Rimes. | Claire Kenyon, Nicolas Schabanel |
| 1999 | Recovering Branches on the Tree of Life: An Approximation Algorithm. | Paul E. Kearney, Ming Li, John Tsang, Tao Jiang |
| 1999 | Optimal On-line Algorithms for an Electronic Commerce Money Distribution System. | Hiroshi Kawazoe, Tetsuo Shibuya, Takeshi Tokuyama |