| 1998 | A 3/2-Approximation Algorithm for Sorting by Reversals. David A. Christie |
| 1998 | A Faster Algorithm for Minimum Cost Submodular Flows. Satoru Iwata, S. Thomas McCormick, Maiko Shigeno |
| 1998 | A New Approximation Algorithm for the Planar Augmentation Problem. Sergej Fialko, Petra Mutzel |
| 1998 | A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem. Naveen Garg, Goran Konjevod, R. Ravi |
| 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 | A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP. Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Woloszyn |
| 1998 | A Probabilistic Algorithm for Updating Files over a Communication Link. Alexandre V. Evfimievski |
| 1998 | Algorithms for the Maxium Subarray Problem Based on Matrix Multiplication. Hisao Tamaki, Takeshi Tokuyama |
| 1998 | An Efficient Algorithm for the Three-Dimensional Diameter Problem. Sergei Bespamyatnikh |
| 1998 | An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems. Martin W. P. Savelsbergh, R. N. Uma, Joel Wein |
| 1998 | Analysis of First-Come-First-Serve Parallel Job Scheduling. Uwe Schwiegelshohn, Ramin Yahyapour |
| 1998 | Analysis of Random Processes via And-Or Tree Evaluation. Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi |
| 1998 | Analysis of a Local Search Heuristic for Facility Location Problems. Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman |
| 1998 | Ancient and New Algorithms for Load Balancing in the L Adi Avidor, Yossi Azar, Jirí Sgall |
| 1998 | Approximate Polynomials Gcds, Padé Approximation, Polynomial Zeros and Bipartite Graphs. Victor Y. Pan |
| 1998 | Approximate String Matching: A Simpler Faster Algorithm. Richard Cole, Ramesh Hariharan |
| 1998 | Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint. Uri Zwick |
| 1998 | Approximation Algorithms for Directed Steiner Problems. Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li |
| 1998 | Augmenting Undirected Edge Connectivity in Õ(n András A. Benczúr, David R. Karger |
| 1998 | Authoritative Sources in a Hyperlinked Environment. Jon M. Kleinberg |
| 1998 | Average-Case Analyses of First Fit and Random Fit Bin Packing. Susanne Albers, Michael Mitzenmacher |
| 1998 | Beating the 2 Delta Bound for Approximately Counting Colourings: A Computer-Assisted Proof of Rapid Mixing. Russ Bubley, Martin E. Dyer, Catherine S. Greenhill |
| 1998 | Better Random Sampling Algorithms for Flows in Undirected Graphs. David R. Karger |
| 1998 | Bounding the Diffuse Adversary. Neal E. Young |
| 1998 | Collision Detection in Aspect and Scale Bounded Polyhedra. Subhash Suri, Philip M. Hubbard, John F. Hughes |
| 1998 | Competive Algorithms for Multilevel Caching and Relaxed List Update (Extended Abstract). Marek Chrobak, John Noga |
| 1998 | Computation in Noisy Radio Networks. Eyal Kushilevitz, Yishay Mansour |
| 1998 | Computing Univariate GCDs over Number Fields. Michael B. Monagan, Roger Margot |
| 1998 | Direct Routing on Trees (Extended Abstract). Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup |
| 1998 | Edge-Connectivity Augmentation with Partition Constraints. Jørgen Bang-Jensen, Harold N. Gabow, Tibor Jordán, Zoltán Szigeti |
| 1998 | Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries. Peter Bro Miltersen |
| 1998 | Exact Arithmetic at Low Cost - A Case Study in Linear Programming. Bernd Gärtner |
| 1998 | Exact and Approximation Algorithms for Clustering (Extended Abstract). Pankaj K. Agarwal, Cecilia Magdalena Procopiuc |
| 1998 | Exploring Unknown Undirected Graphs. Petrisor Panaite, Andrzej Pelc |
| 1998 | Extended Hilbert Irreducibility and its Applications. Ming-Deh A. Huang, Yiu-Chung Wong |
| 1998 | Fast Backtracking Principles Applied to Find New Cages. Brendan D. McKay, Wendy J. Myrvold, Jacqueline Nadon |
| 1998 | Fast Distributed Algorithms for {Brooks-Vizing} Colourings. David A. Grable, Alessandro Panconesi |
| 1998 | Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs. David Eppstein |
| 1998 | Faster Algorithms for the Quickest Transshipment Problem with Zero Transit Times. Lisa Fleischer |
| 1998 | Faster Deterministic Sorting and Priority Queues in Linear Space. Mikkel Thorup |
| 1998 | Faster Random Generation of Linear Extensions. Russ Bubley, Martin E. Dyer |
| 1998 | Finding a Large Hidden Clique in a Random Graph. Noga Alon, Michael Krivelevich, Benny Sudakov |
| 1998 | Finger Search Trees with Constant Insertion Time. Gerth Stølting Brodal |
| 1998 | Flow and Stretch Metrics for Scheduling Continuous Job Streams. Michael A. Bender, Soumen Chakrabarti, S. Muthukrishnan |
| 1998 | Go with the Winners for Graph Bisection. Tassos Dimitriou, Russell Impagliazzo |
| 1998 | Greedy Strikes Back: Improved Facility Location Algorithms. Sudipto Guha, Samir Khuller |
| 1998 | Hiding Cliques for Cryptographic Security. Ari Juels, Marcus Peinado |
| 1998 | I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking (Extended Abstract). Pankaj K. Agarwal, Lars Arge, T. M. Murali, Kasturi R. Varadarajan, Jeffrey Scott Vitter |
| 1998 | Identification of Gene Regulatory Networks by Strategic Gene Disruptions and Gene Overexpressions. Tatsuya Akutsu, Satoru Kuhara, Osamu Maruyama, Satoru Miyano |
| 1998 | Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles (Extended Abstract). Pankaj K. Agarwal, Jeff Erickson, Leonidas J. Guibas |
| 1998 | LRU is Better than FIFO. Marek Chrobak, John Noga |
| 1998 | Learning Deterministic Finite Automata from Smallest Counterexamples. Andreas Birkendorf, Andreas Böker, Hans Ulrich Simon |
| 1998 | Linear-Time Register Allocation for a Fixed Number of Registers. Hans L. Bodlaender, Jens Gustedt, Jan Arne Telle |
| 1998 | Matroid Decomposition Methods for the Set Maxima Problem. Vincenzo Liberatore |
| 1998 | Minimizing Service and Operation Costs of Periodic Scheduling (Extended Abstract). Amotz Bar-Noy, Randeep Bhatia, Joseph Naor, Baruch Schieber |
| 1998 | Multi-Item Inventory Staggering Problems: Heuristic and Bounds. Chung-Piaw Teo, Jihong Ou, Kok-Choon Tan |
| 1998 | Mutual Search (Extended Abstract). Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi |
| 1998 | New Approximation Techniques for Some Ordering Problems. Satish Rao, Andréa W. Richa |
| 1998 | On Approximating Rectangle Tiling and Packing. Sanjeev Khanna, S. Muthukrishnan, Mike Paterson |
| 1998 | On Local Register Allocation. Martin Farach, Vincenzo Liberatore |
| 1998 | On the Distributed Complexity of Computing Maximal Matchings. Michal Hanckowiak, Michal Karonski, Alessandro Panconesi |
| 1998 | On the Exact Worst Case Query Complexity of Planar Point Location. Udo Adamy, Raimund Seidel |
| 1998 | On-Line File Caching. Neal E. Young |
| 1998 | On-line Randomized Call Control Revisited. Stefano Leonardi, Alberto Marchetti-Spaccamela, Alessio Presciutti, Adi Rosén |
| 1998 | Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control. Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin |
| 1998 | Optimal Augmentation to Make a Graph k-Edge-Connected and Triconnected. Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki |
| 1998 | Optimal Edge Ranking of Trees in Linear Time. Tak Wah Lam, Fung Ling Yue |
| 1998 | Output-Sensitive Generation of Random Events. Paul B. Callahan |
| 1998 | Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 25-27 January 1998, San Francisco, California, USA. Howard J. Karloff |
| 1998 | Reconstructing Randomly Sampled Multivariate Polynomials from Highly Noisy Data. Hal Wasserman |
| 1998 | Ring Routing and Wavelength Translation. Gordon T. Wilfong, Peter Winkler |
| 1998 | Sparse 0-1-Matrices and Forbidden Hypergraphs (Extended Abstract). Claudia Bertram-Kretzberg, Thomas Hofmeister, Hanno Lefmann |
| 1998 | Spatial Codes and the Hardness of String Folding Problems (Extended Abstract). Ashwin Nayak, Alistair Sinclair, Uri Zwick |
| 1998 | The Analysis of Hybrid Trie Structures. Julien Clément, Philippe Flajolet, Brigitte Vallée |
| 1998 | The Dynamic Servers Problem. Moses Charikar, Dan Halperin, Rajeev Motwani |
| 1998 | The Maximum Subforest Problem: Approximation and Exact Algorithms (Extended Abstract). Ron Shamir, Dekel Tsur |
| 1998 | The Power of Migration in Multi-Processor Scheduling of Real-Time Systems. Gilad Koren, Amihood Amir, Emanuel Dar |
| 1998 | The Ultimate Interval Graph Recognition Algorithm? (Extended Abstract). Derek G. Corneil, Stephan Olariu, Lorna Stewart |
| 1998 | Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems (Extended Abstract). Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter |
| 1998 | Two New Upper Bounds for SAT. Edward A. Hirsch |