| 1999 | A New Way to Use Semidefinite Programming with Applications to Linear Equations mod | Gunnar Andersson, Lars Engebretsen, Johan Hstad |
| 1999 | Playing Twenty Questions with a Procrastinator. | Andris Ambainis, Stephen A. Bloch, David L. Schweizer |
| 1999 | Exploring Unknown Environments with Obstacles. | Susanne Albers, Klaus Kursawe, Sven Schuierer |
| 1999 | Page Replacement for General Caching Problems. | Susanne Albers, Sanjeev Arora, Sanjeev Khanna |
| 1999 | Motion Planning of a Ball Amid Segments in Three Dimensions. | Pankaj K. Agarwal, Micha Sharir |
| 1999 | I/O-Efficient Dynamic Point Location in Monotone Planar Subdivisions. | Pankaj K. Agarwal, Lars Arge, Gerth Stlting Brodal, Jeffrey Scott Vitter |
| 1999 | Inverse Inbreeding Coefficient Problems with an Application to Linkage Analysis of Recessive Diseases in Inbred Populations. | Richa Agarwala, Leslie G. Biesecker, Alejandro A. Schffer |
| 1999 | Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms. | Ran Adler, Yossi Azar |
| 1998 | Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint. | Uri Zwick |
| 1998 | Bounding the Diffuse Adversary. | Neal E. Young |
| 1998 | On-Line File Caching. | Neal E. Young |
| 1998 | A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees. | Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, R. Ravi, Chuan Yi Tang |
| 1998 | Ring Routing and Wavelength Translation. | Gordon T. Wilfong, Peter Winkler |
| 1998 | Reconstructing Randomly Sampled Multivariate Polynomials from Highly Noisy Data. | Hal Wasserman |
| 1998 | Faster Deterministic Sorting and Priority Queues in Linear Space. | Mikkel Thorup |
| 1998 | Multi-Item Inventory Staggering Problems: Heuristic and Bounds. | Chung-Piaw Teo, Jihong Ou, Kok-Choon Tan |
| 1998 | Algorithms for the Maxium Subarray Problem Based on Matrix Multiplication. | Hisao Tamaki, Takeshi Tokuyama |
| 1998 | Collision Detection in Aspect and Scale Bounded Polyhedra. | Subhash Suri, Philip M. Hubbard, John F. Hughes |
| 1998 | The Maximum Subforest Problem: Approximation and Exact Algorithms (Extended Abstract). | Ron Shamir, Dekel Tsur |
| 1998 | Analysis of First-Come-First-Serve Parallel Job Scheduling. | Uwe Schwiegelshohn, Ramin Yahyapour |
| 1998 | An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems. | Martin W. P. Savelsbergh, R. N. Uma, Joel Wein |
| 1998 | New Approximation Techniques for Some Ordering Problems. | Satish Rao, Andra W. Richa |
| 1998 | Exploring Unknown Undirected Graphs. | Petrisor Panaite, Andrzej Pelc |
| 1998 | Approximate Polynomials Gcds, Pad Approximation, Polynomial Zeros and Bipartite Graphs. | Victor Y. Pan |
| 1998 | Spatial Codes and the Hardness of String Folding Problems (Extended Abstract). | Ashwin Nayak, Alistair Sinclair, Uri Zwick |