| 1999 | Reconstructing Set Partitions. | Vladimir Grebinski, Gregory Kucherov |
| 1999 | Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control. | Michael H. Goldwasser |
| 1999 | Combinatorial Algorithms Test Sets [CATS]: The ACM/EATCS Platform for Experimental Research. | Andrew V. Goldberg, Bernard M. E. Moret |
| 1999 | Cut Tree Algorithms. | Andrew V. Goldberg, Kostas Tsioutsiouliklis |
| 1999 | The Complexity of Gene Placement. | Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel A. Pevzner, Sleyman Cenk Sahinalp, Elizabeth Sweedyk |
| 1999 | Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. | Michel X. Goemans, David P. Williamson |
| 1999 | Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing. | Ashish Goel |
| 1999 | Synopsis Data Structures for Massive Data Sets. | Phillip B. Gibbons, Yossi Matias |
| 1999 | Algorithms for Compile-Time Memory Optimization. | Jordan Gergov |
| 1999 | Efficient Approximation Algorithms for the Hamming Center Problem. | Leszek Gasieniec, Jesper Jansson, Andrzej Lingas |
| 1999 | How to Make a Square Grid Framework with Cables Rigid. | Harold N. Gabow, Tibor Jordn |
| 1999 | Randomized Splay Trees. | Martin Frer |
| 1999 | Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs. | Alan M. Frieze, Lei Zhao |
| 1999 | Checking Priority Queues. | Ulrich Finkler, Kurt Mehlhorn |
| 1999 | Optimal Node-Degree Bounds for the Complexity of Nonplanarity Parameters. | Celina M. H. de Figueiredo, Lurbio Faria, Candido Ferreira Xavier de Mendona Neto |
| 1999 | Simplicity and Hardness of the Maximum Traveling Salesman Problem Under Geometric Distances. | Sndor P. Fekete |
| 1999 | Separation-Sensitive Collision Detection for Convex Objects. | Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi, Li Zhang |
| 1999 | Randomized Online Scheduling on Two Uniform Machines. | Leah Epstein, John Noga, Steven S. Seiden, Jir Sgall, Gerhard J. Woeginger |
| 1999 | Shortest Paths in an Arrangement with | David Eppstein, David Hart |
| 1999 | Incremental and Decremental Maintenance of Planar Width. | David Eppstein |
| 1999 | Balanced Aspect Ratio Trees: Combining the Advantages of | Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov |
| 1999 | Clustering in Large Graphs and Matrices. | Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, V. Vinay |
| 1999 | The 2-Catalog Segmentation Problem. | Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna |
| 1999 | A Simple Provable Algorithm for Curve Reconstruction. | Tamal K. Dey, Piyush Kumar |
| 1999 | Folding and One Straight Cut Suffice. | Erik D. Demaine, Martin L. Demaine, Anna Lubiw |