| 1999 | Parametric Polymatroid Optimization and Its Geometric Applications. | Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama |
| 1999 | Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. | Haim Kaplan, Martin Strauss, Mario Szegedy |
| 1999 | On-line Complexity of Monotone Set Systems. | Haim Kaplan, Mario Szegedy |
| 1999 | Designing Proxies for Stock Market Indices is Computationally Hard. | Ming-Yang Kao, Stephen R. Tate |
| 1999 | Computing Nearest Neighbors for Moving Points and Applications to Clustering. | Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y. Wu |
| 1999 | Eliminating Migration in Multi-Processor Scheduling. | Bala Kalyanasundaram, Kirk Pruhs |
| 1999 | A Generalized | Anna M. Johnston |
| 1999 | What are the Least Tractable Instances of max Independent Set? | David S. Johnson, Mario Szegedy |
| 1999 | Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks. | Klaus Jansen, Lorant Porkolab |
| 1999 | A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem. | Kamal Jain, Ion I. Mandoiu, Vijay V. Vazirani, David P. Williamson |
| 1999 | Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation. | Satoru Iwata |
| 1999 | An O(N) Oblivious Routing Algorithm for 2-D Meshes of Constant Queue-Size. | Kazuo Iwama, Eiji Miyano |
| 1999 | The Phase Transition in Random Horn Satisfiability and Its Algorithmic Implications. | Gabriel Istrate |
| 1999 | Geometric Matching Under Noise: Combinatorial Bounds and Algorithms. | Piotr Indyk, Rajeev Motwani, Suresh Venkatasubramanian |
| 1999 | A Small Approximately min-wise Independent Family of Hash Functions. | Piotr Indyk |
| 1999 | Fully Dynamic Algorithms for Chordal Graphs. | Louis Ibarra |
| 1999 | Efficient Exact Sampling from the Ising Model Using Swendsen-Wang. | Mark Huber |
| 1999 | A 1.598 Approximation Algorithm for the Steiner Problem in Graphs. | Stefan Hougardy, Hans Jrgen Prmel |
| 1999 | Scheduling Multicasts on Unit-Capacity Trees and Meshes. | Monika Rauch Henzinger, Stefano Leonardi |
| 1999 | Dynamical System Representation of Open Address Hash Functions. | Gregory L. Heileman, Chaouki T. Abdallah, Bernard M. E. Moret, Bradley J. Smith |
| 1999 | New Algorithms for Generating Conway Polynomials Over Finite Fields. | Lenwood S. Heath, Nicholas A. Loehr |
| 1999 | Parallel Integer Sorting is More Efficient than Parallel Comparison Sorting on Exclusive Write PRAMs. | Yijie Han, Xiaojun Shen |
| 1999 | Online Coloring Known Graphs. | Magns M. Halldrsson |
| 1999 | Fast Deterministic Construction of Static Dictionaries. | Torben Hagerup |
| 1999 | Estimating Interpolation Error: A Combinatorial Approach. | Stephen Guattery, Gary L. Miller, Noel Walkington |