| 1998 | Computing Univariate GCDs over Number Fields. | Michael B. Monagan, Roger Margot |
| 1998 | Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries. | Peter Bro Miltersen |
| 1998 | Fast Backtracking Principles Applied to Find New Cages. | Brendan D. McKay, Wendy J. Myrvold, Jacqueline Nadon |
| 1998 | Analysis of Random Processes via And-Or Tree Evaluation. | Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi |
| 1998 | Matroid Decomposition Methods for the Set Maxima Problem. | Vincenzo Liberatore |
| 1998 | On-line Randomized Call Control Revisited. | Stefano Leonardi, Alberto Marchetti-Spaccamela, Alessio Presciutti, Adi Rosn |
| 1998 | Optimal Edge Ranking of Trees in Linear Time. | Tak Wah Lam, Fung Ling Yue |
| 1998 | Computation in Noisy Radio Networks. | Eyal Kushilevitz, Yishay Mansour |
| 1998 | Analysis of a Local Search Heuristic for Facility Location Problems. | Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman |
| 1998 | The Power of Migration in Multi-Processor Scheduling of Real-Time Systems. | Gilad Koren, Amihood Amir, Emanuel Dar |
| 1998 | Authoritative Sources in a Hyperlinked Environment. | Jon M. Kleinberg |
| 1998 | On Approximating Rectangle Tiling and Packing. | Sanjeev Khanna, S. Muthukrishnan, Mike Paterson |
| 1998 | Better Random Sampling Algorithms for Flows in Undirected Graphs. | David R. Karger |
| 1998 | Hiding Cliques for Cryptographic Security. | Ari Juels, Marcus Peinado |
| 1998 | A Faster Algorithm for Minimum Cost Submodular Flows. | Satoru Iwata, S. Thomas McCormick, Maiko Shigeno |
| 1998 | Optimal Augmentation to Make a Graph k-Edge-Connected and Triconnected. | Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki |
| 1998 | Extended Hilbert Irreducibility and its Applications. | Ming-Deh A. Huang, Yiu-Chung Wong |
| 1998 | Two New Upper Bounds for SAT. | Edward A. Hirsch |
| 1998 | On the Distributed Complexity of Computing Maximal Matchings. | Michal Hanckowiak, Michal Karonski, Alessandro Panconesi |
| 1998 | Greedy Strikes Back: Improved Facility Location Algorithms. | Sudipto Guha, Samir Khuller |
| 1998 | Fast Distributed Algorithms for {Brooks-Vizing} Colourings. | David A. Grable, Alessandro Panconesi |
| 1998 | Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control. | Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin |
| 1998 | Exact Arithmetic at Low Cost - A Case Study in Linear Programming. | Bernd Grtner |
| 1998 | A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. | Naveen Garg, Goran Konjevod, R. Ravi |
| 1998 | Faster Algorithms for the Quickest Transshipment Problem with Zero Transit Times. | Lisa Fleischer |