| 1999 | Approximation Algorithms for Restoration Capacity Planning. | Steven J. Phillips, Jeffery R. Westbrook |
| 1999 | Random Cayley Graphs with O(log[G]) Generators Are Expanders. | Igor Pak |
| 1999 | Motif Statistics. | Pierre Nicodme, Bruno Salvy, Philippe Flajolet |
| 1999 | Efficient Searching for Multi-dimensional Data Made Simple. | Enrico Nardelli, Maurizio Talamo, Paola Vocca |
| 1999 | A Polyhedral Algorithm for Packings and Designs. | Lucia Moura |
| 1999 | Resource-Constrained Project Scheduling: Computing Lower Bounds by Solving Minimum Cut Problems. | Rolf H. Mhring, Andreas S. Schulz, Frederik Stork, Marc Uetz |
| 1999 | Efficient Algorithms foe On-Line Symbol Ranking Compression. | Giovanni Manzini |
| 1999 | Strategies for Searching with Different Access Costs. | Eduardo Sany Laber, Ruy Luiz Milidi, Artur Alves Pessoa |
| 1999 | Efficient Approximation Algorithms for the Achromatic Number. | Piotr Krysta, Krzysztof Lorys |
| 1999 | How Long Does a Bit Live in a Computer? (abstract). | Bernhard Korte |
| 1999 | A Nearly Linear-Time Approximation Scheme for the Euclidean kappa-median Problem. | Stavros G. Kolliopoulos, Satish Rao |
| 1999 | A Decomposition Theorem for Maximum Weight Bipartite Matchings with Applications to Evolutionary Trees. | Ming-Yang Kao, Tak Wah Lam, Wing-Kin Sung, Hing-Fung Ting |
| 1999 | On the Analysis of Evolutionary Algorithms - A Proof That Crossover Really Can Help. | Thomas Jansen, Ingo Wegener |
| 1999 | Multipacket Routing on 2-D Meshes and Its Application to Fault-Tolerant Routing. | Kazuo Iwama, Eiji Miyano |
| 1999 | Augmenting a (kappa-1)-Vertex-Connected Multigraph to an iota-Edge-Connected and kappa-Vertex-Connected Multigraph. | Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki |
| 1999 | Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices. | Volker Heun |
| 1999 | A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs. | Pavol Hell, Ron Shamir, Roded Sharan |
| 1999 | A Fast General Methodology for Information - Theoretically Optimal Encodings of Graphs. | Xin He, Ming-Yang Kao, Hsueh-I Lu |
| 1999 | Provably Good and Practical Strategies for Non-Uniform Data Management in Networks. | Friedhelm Meyer auf der Heide, Berthold Vcking, Matthias Westermann |
| 1999 | Fast and Robust Smallest Enclosing Balls. | Bernd Grtner |
| 1999 | Adaptively-Secure Distributed Public-Key Systems. | Yair Frankel, Philip D. MacKenzie, Moti Yung |
| 1999 | On Computing the Diameter of a Point Set in High Dimensional Euclidean Space. | Daniele V. Finocchiaro, Marco Pellegrini |
| 1999 | Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines. | Leah Epstein, Jir Sgall |
| 1999 | Faster Exact Solutions for Some NP-Hard Problems. | Limor Drori, David Peleg |
| 1999 | The Impact of Knowledge on Broadcasting Time in Radio Networks. | Krzysztof Diks, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc |