| 1999 | A 1.598 Approximation Algorithm for the Steiner Problem in Graphs. Stefan Hougardy, Hans Jürgen Prömel |
| 1999 | A Convex Relaxation for the Asymmetric TSP. Santosh S. Vempala, Mihalis Yannakakis |
| 1999 | A Deterministic Approximation Algorithm for a Minmax Integer Programming Problem. Chi-Jen Lu |
| 1999 | A Formal Treatment of Remotely Keyed Encryption. Matt Blaze, Joan Feigenbaum, Moni Naor |
| 1999 | A Generalization of Janson Inequalities and its Application to Finding Shortest Paths. C. R. Subramanian |
| 1999 | A Generalized Anna M. Johnston |
| 1999 | A Lower Bound for Hellbronn's Triangle Problem in Gill Barequet |
| 1999 | A Near-Linear Area Bound for Drawing Binary Trees. Timothy M. Chan |
| 1999 | A New Property and a Faster Algorithm for Baseball Elimination. Kevin D. Wayne |
| 1999 | A New Way to Use Semidefinite Programming with Applications to Linear Equations mod Gunnar Andersson, Lars Engebretsen, Johan Håstad |
| 1999 | A Practical Clustering Algorithm for Static and Dynamic Information Organization. Javed A. Aslam, Katya Pelekhov, Daniela Rus |
| 1999 | A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem. Kamal Jain, Ion I. Mandoiu, Vijay V. Vazirani, David P. Williamson |
| 1999 | A Simple Provable Algorithm for Curve Reconstruction. Tamal K. Dey, Piyush Kumar |
| 1999 | A Slique Size Bounding Technique with Application to Non-Linear Codes. Mario Szegedy |
| 1999 | A Small Approximately min-wise Independent Family of Hash Functions. Piotr Indyk |
| 1999 | A Small Universal Graph for Bounded-degree Planar Graphs. Michael R. Capalbo |
| 1999 | A Uniform Framework for Approximating Weighted Connectivity Problems. Samir Khuller, Balaji Raghavachari, An Zhu |
| 1999 | A Wide-Range Efficient Algorithm for Minimal Triangulation. Anne Berry |
| 1999 | Algorithms for Compile-Time Memory Optimization. Jordan Gergov |
| 1999 | Algorithms for Total Weighted Completion Time Scheduling. Ivan D. Baev, Waleed Meleis, Alexandre E. Eichenberger |
| 1999 | All-to-All Optical Routing in Optimal Chordal Rings of Degree Four. Lata Narayanan, Jaroslav Opatrny, Dominique Sotteau |
| 1999 | An Algorithm to Symbolically Describe Flows on Surfaces. Luis-Miguel Lopez, Philippe Narbel |
| 1999 | An Analysis of the Burrows-Wheeler Transform. Giovanni Manzini |
| 1999 | An Efficient Algorithm for Computing the Jeffrey O. Shallit, David Swart |
| 1999 | An Efficient Algorithm for Generating Necklaces with Fixed Density. Joe Sawada, Frank Ruskey |
| 1999 | An O(N) Oblivious Routing Algorithm for 2-D Meshes of Constant Queue-Size. Kazuo Iwama, Eiji Miyano |
| 1999 | An Oracle-Polynomial Time Augmentation Algorithm for Integer Programming. Andreas S. Schulz, Robert Weismantel |
| 1999 | Analysis of a Bounding Box Heuristic for Object Intersection. Yunhong Zhou, Subhash Suri |
| 1999 | Approximability of Scheduling with Fixed Jobs. Mark Scharbrodt, Angelika Steger, Horst Weisser |
| 1999 | Approximate Minimum Weight Steiner Triangulation in Three Dimensions. Siu-Wing Cheng, Tamal K. Dey |
| 1999 | Approximating Multiroot 3-Outconnected Subgraphs. Zeev Nutov |
| 1999 | Approximation Algorithms for Bipartite and Non-Bipartite Matching in the Plane. Kasturi R. Varadarajan, Pankaj K. Agarwal |
| 1999 | Approximation Algorithms for Protein Folding Prediction. Giancarlo Mauri, Giulio Pavesi, Antonio Piccolboni |
| 1999 | Approximation Algorithms for the Asymmetric Postman Problem. Balaji Raghavachari, Jeyakesavan Veerasamy |
| 1999 | Balanced Aspect Ratio Trees: Combining the Advantages of Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov |
| 1999 | Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms. Ran Adler, Yossi Azar |
| 1999 | Cache Performance Analysis of Traversals and Random Accesses. Richard E. Ladner, James D. Fix, Anthony LaMarca |
| 1999 | Certified Computation of the Sign of a Matrix Determinant. Victor Y. Pan, Yanqiang Yu |
| 1999 | Checking Priority Queues. Ulrich Finkler, Kurt Mehlhorn |
| 1999 | Clustering in Large Graphs and Matrices. Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, V. Vinay |
| 1999 | Colouring Graphs with Prescribed Induced Cycle Lengths. Ingo Schiermeyer, Bert Randerath |
| 1999 | Combinatorial Algorithms Test Sets [CATS]: The ACM/EATCS Platform for Experimental Research. Andrew V. Goldberg, Bernard M. E. Moret |
| 1999 | Combinatorial Approximation Algorithms for Generalized Flow Problems. Jeffrey D. Oldham |
| 1999 | Combinatorics Helps for Hexahedral Mesh Generation in CAD. Matthias Müller-Hannemann |
| 1999 | Compact Roundtrip Routing for Digraphs. Lenore Cowen, Christopher G. Wagner |
| 1999 | Compact Routing with Minimum Stretch. Lenore Cowen |
| 1999 | Compass Permits Leader Election. Jacques Mazoyer, Codrin M. Nichitiu, Eric Rémila |
| 1999 | Computational Complexity of Compaction to Cycles. Narayan Vikas |
| 1999 | Computing Morse Functions on Triangulated Manifolds. Ulrike Axen |
| 1999 | Computing Nearest Neighbors for Moving Points and Applications to Clustering. Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y. Wu |
| 1999 | Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation. Satoru Iwata |
| 1999 | Cooperative Sharing and Asynchronous Consensus Using Single-Reader Single-Writer Registers. Yonatan Aumann, Avivit Kapah-Levy |
| 1999 | Cut Tree Algorithms. Andrew V. Goldberg, Kostas Tsioutsiouliklis |
| 1999 | Delayed Path Coupling and Generating Random Permutations via Distributed Stochastic Processes. Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, Krzysztof Lorys |
| 1999 | Designing Proxies for Stock Market Indices is Computationally Hard. Ming-Yang Kao, Stephen R. Tate |
| 1999 | Distinguishing String Selection Problems. J. Kevin Lanctôt, Ming Li, Bin Ma, Shaojiu Wang, Louxin Zhang |
| 1999 | Dual-Issue Scheduling with Spills for Binary Trees. Waleed Meleis, Edward S. Davidson |
| 1999 | Dynamic LCA Queries on Trees. Richard Cole, Ramesh Hariharan |
| 1999 | Dynamical System Representation of Open Address Hash Functions. Gregory L. Heileman, Chaouki T. Abdallah, Bernard M. E. Moret, Bradley J. Smith |
| 1999 | Efficient Algorithms for Petersen's Matching Theorem. Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, Anna Lubiw |
| 1999 | Efficient Approximation Algorithms for the Hamming Center Problem. Leszek Gasieniec, Jesper Jansson, Andrzej Lingas |
| 1999 | Efficient Exact Sampling from the Ising Model Using Swendsen-Wang. Mark Huber |
| 1999 | Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions. Gill Barequet, Sariel Har-Peled |
| 1999 | Eliminating Migration in Multi-Processor Scheduling. Bala Kalyanasundaram, Kirk Pruhs |
| 1999 | Empirical Investigation of the Markov Reference Model. Vincenzo Liberatore |
| 1999 | Emulations Between QSM, BSP, and LogP: A Framework for General-Purpose Parallel Algorithm Design. Vijaya Ramachandran, Brian Grayson, Michael Dahlin |
| 1999 | Estimating Interpolation Error: A Combinatorial Approach. Stephen Guattery, Gary L. Miller, Noel Walkington |
| 1999 | Exact Solutions to Large-scale Plane Steiner Tree Problems. David M. Warme, Pawel Winter, Martin Zachariasen |
| 1999 | Existence of Multiplicative Secret Sharing Schemes with Polynomial Share Expansion. Giovanni Di Crescenzo, Yair Frankel |
| 1999 | Experimental Performance of Shared RSA Modulus Generation. Rebecca N. Wright, Sara Spalding |
| 1999 | Exploring Unknown Environments with Obstacles. Susanne Albers, Klaus Kursawe, Sven Schuierer |
| 1999 | Fast Algorithms for Constructing Optimal Trees from Quartets. David Bryant, Mike A. Steel |
| 1999 | Fast Deterministic Construction of Static Dictionaries. Torben Hagerup |
| 1999 | Fast and Effective Stripification of Polygonal Surface Models. Xinyu Xiang, Martin Held, Joseph S. B. Mitchell |
| 1999 | Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks. Yair Bartal, Martin Farach-Colton, Shibu Yooseph, Lisa Zhang |
| 1999 | Faster Approximation Algorithms for Generalized Flow. Kevin D. Wayne, Lisa Fleischer |
| 1999 | Finding Maximum Independent Sets in Sparse and General Graphs. Richard Beigel |
| 1999 | Fluid Limits, Bin Packing, and Stochastic Analysis of Algorithms. Edward G. Coffman Jr., Alexander L. Stolyar |
| 1999 | Folding and One Straight Cut Suffice. Erik D. Demaine, Martin L. Demaine, Anna Lubiw |
| 1999 | Fully Dynamic Algorithms for Chordal Graphs. Louis Ibarra |
| 1999 | Geometric Matching Under Noise: Combinatorial Bounds and Algorithms. Piotr Indyk, Rajeev Motwani, Suresh Venkatasubramanian |
| 1999 | Greedy Algorithms for Optimized DNA Sequencing. Allon G. Percus, David C. Torney |
| 1999 | Greedy Local Improvement and Weighted Set Packing Approximation. Barun Chandra, Magnús M. Halldórsson |
| 1999 | Group Signatures Giuseppe Ateniese, Gene Tsudik |
| 1999 | How to Make a Square Grid Framework with Cables Rigid. Harold N. Gabow, Tibor Jordán |
| 1999 | I/O-Complexity of Graph Algorithms. Kamesh Munagala, Abhiram G. Ranade |
| 1999 | I/O-Efficient Dynamic Point Location in Monotone Planar Subdivisions. Pankaj K. Agarwal, Lars Arge, Gerth Stølting Brodal, Jeffrey Scott Vitter |
| 1999 | Improved Approximation Algorithms for a Capacitated Facility Location Problem. Fabián A. Chudak, David B. Shmoys |
| 1999 | Improved Bicriteria Existence Theorems for Scheduling. Javed A. Aslam, April Rasala, Clifford Stein, Neal E. Young |
| 1999 | Incremental and Decremental Maintenance of Planar Width. David Eppstein |
| 1999 | Indexing Schemes for Random Points. Elias Koutsoupias, David Scot Taylor |
| 1999 | Interleaved Prefetching. Tracy Kimbrel |
| 1999 | Inverse Inbreeding Coefficient Problems with an Application to Linkage Analysis of Recessive Diseases in Inbred Populations. Richa Agarwala, Leslie G. Biesecker, Alejandro A. Schäffer |
| 1999 | Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. Haim Kaplan, Martin Strauss, Mario Szegedy |
| 1999 | Kinetic Collision Detection Between Two Simple Polygons. Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang |
| 1999 | LBFS Orderings and Cocomparability Graphs. Derek G. Corneil, Stephan Olariu, Lorna Stewart |
| 1999 | LP-based Analysis of Greedy-dual-size. Edith Cohen, Haim Kaplan |
| 1999 | Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks. Klaus Jansen, Lorant Porkolab |
| 1999 | Locally Efficient On-Line Strategies for Routing Packets Along Fixed Paths. Petra Berenbrink, Christian Scheideler |
| 1999 | Locked and Unlocked Polygonal Chains in 3D. Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark H. Overmars, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides |
| 1999 | Lower Bounds for SRPT-Subsequence Algorithms for Nonpreemptive Scheduling. Eric Torng, Patchrawat Uthaisombut |
| 1999 | Median Bounds and Their Application. Alan Siegel |
| 1999 | Minimizing Weighted Completion Time on a Single Machine. Chandra Chekuri, Rajeev Motwani |
| 1999 | Minimizing Wirelength in Zero and Bounded Skew Clock Trees. Moses Charikar, Jon M. Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins |
| 1999 | Motion Planning of a Ball Amid Segments in Three Dimensions. Pankaj K. Agarwal, Micha Sharir |
| 1999 | New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. Frank Thomson Leighton, Satish Rao, Aravind Srinivasan |
| 1999 | New Algorithms for Generating Conway Polynomials Over Finite Fields. Lenwood S. Heath, Nicholas A. Loehr |
| 1999 | Nonplanar Topological Inference and Political-Map Graphs. Zhi-Zhong Chen, Xin He, Ming-Yang Kao |
| 1999 | On Approximability of the Minimum-Cost Artur Czumaj, Andrzej Lingas |
| 1999 | On Multi-Dimensional Packing Problems. Chandra Chekuri, Sanjeev Khanna |
| 1999 | On the Bidirected Cut Relaxation for the Metric Steiner Tree Problem. Sridhar Rajagopalan, Vijay V. Vazirani |
| 1999 | On the Optimality of Parsing in Dynamic Dictionary Based Data Compression. Yossi Matias, Süleyman Cenk Sahinalp |
| 1999 | On the Parallel Time Complexity of Undirected Connectivity and Minimum Spanning Trees. Ka Wong Chong, Yijie Han, Tak Wah Lam |
| 1999 | On-line Complexity of Monotone Set Systems. Haim Kaplan, Mario Szegedy |
| 1999 | Online Coloring Known Graphs. Magnús M. Halldórsson |
| 1999 | Online Resource Minimization. Anton J. Kleywegt, Vijay S. Nori, Martin W. P. Savelsbergh, Craig A. Tovey |
| 1999 | Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs. Alan M. Frieze, Lei Zhao |
| 1999 | Optimal Multichannel Communication Under Failure. Tanya Y. Berger-Wolf, Edward M. Reingold |
| 1999 | Optimal Node-Degree Bounds for the Complexity of Nonplanarity Parameters. Celina M. H. de Figueiredo, Luérbio Faria, Candido Ferreira Xavier de Mendonça Neto |
| 1999 | Optimal On-line Algorithms for an Electronic Commerce Money Distribution System. Hiroshi Kawazoe, Tetsuo Shibuya, Takeshi Tokuyama |
| 1999 | Optimal Scheduling of Multiclass Parallel Machines. Jay Sethuraman, Mark S. Squillante |
| 1999 | Packet Filtering in High Speed Networks. Subhash Suri, George Varghese |
| 1999 | Page Replacement for General Caching Problems. Susanne Albers, Sanjeev Arora, Sanjeev Khanna |
| 1999 | Parallel Integer Sorting is More Efficient than Parallel Comparison Sorting on Exclusive Write PRAMs. Yijie Han, Xiaojun Shen |
| 1999 | Parallel Virtual Memory. Frank K. H. A. Dehne, Wolfgang Dittrich, David A. Hutchinson, Anil Maheshwari |
| 1999 | Parameterized diff. Brenda S. Baker |
| 1999 | Parametric Polymatroid Optimization and Its Geometric Applications. Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama |
| 1999 | Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control. Michael H. Goldwasser |
| 1999 | Placement Algorithms for Hierarchical Cooperative Caching. Madhukar R. Korupolu, C. Greg Plaxton, Rajmohan Rajaraman |
| 1999 | Playing Twenty Questions with a Procrastinator. Andris Ambainis, Stephen A. Bloch, David L. Schweizer |
| 1999 | Polygon-containment and Translational min-Hausdorff-Distance between segment Sets are 3SUM-hard. Gill Barequet, Sariel Har-Peled |
| 1999 | Preemptive Scheduling with Job-Dependent Setup Times. Petra Schuurman, Gerhard J. Woeginger |
| 1999 | Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland, USA. Robert Endre Tarjan, Tandy J. Warnow |
| 1999 | Queries with Segments in Voronoi Diagrams. Sergei Bespamyatnikh, Jack Snoeyink |
| 1999 | Randomized Online Scheduling on Two Uniform Machines. Leah Epstein, John Noga, Steven S. Seiden, Jirí Sgall, Gerhard J. Woeginger |
| 1999 | Randomized Splay Trees. Martin Fürer |
| 1999 | Reconstructing Set Partitions. Vladimir Grebinski, Gregory Kucherov |
| 1999 | Recovering Branches on the Tree of Life: An Approximation Algorithm. Paul E. Kearney, Ming Li, John Tsang, Tao Jiang |
| 1999 | Recovering Evolutionary Trees Through Harmonic Greedy Triplets. Miklós Csürös, Ming-Yang Kao |
| 1999 | Rectangular Tiling in Multi-dimensional Arrays. Adam Smith, Subhash Suri |
| 1999 | Rendering Equation Revisited: How to Avoid Explicit Visibility Computations. Marco Pellegrini |
| 1999 | Roundness Estimation via Random Sampling. Ravi Kumar, D. Sivakumar |
| 1999 | Sampling Spin Configurations of an Ising System. Dana Randall, David Wilson |
| 1999 | Scheduling Calls for Multicasting in Tree-Networks. Johanne Cohen, Pierre Fraigniaud, Margarida Mitjana |
| 1999 | Scheduling Multicasts on Unit-Capacity Trees and Meshes. Monika Rauch Henzinger, Stefano Leonardi |
| 1999 | Separation-Sensitive Collision Detection for Convex Objects. Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi, Li Zhang |
| 1999 | Shortest Paths in an Arrangement with David Eppstein, David Hart |
| 1999 | Simplicity and Hardness of the Maximum Traveling Salesman Problem Under Geometric Distances. Sándor P. Fekete |
| 1999 | Some Graphic Uses of an Even Number of Odd Nodes. Kathie Cameron, Jack Edmonds |
| 1999 | Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing. Ashish Goel |
| 1999 | Stop Minding Your p's and q's: A Simplified John M. Boyer, Wendy J. Myrvold |
| 1999 | Synopsis Data Structures for Massive Data Sets. Phillip B. Gibbons, Yossi Matias |
| 1999 | The 2-Catalog Segmentation Problem. Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna |
| 1999 | The Advantages of Forward Thinking in Generating Rooted and Free Trees. Gang Li, Frank Ruskey |
| 1999 | The Complexity of Gene Placement. Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel A. Pevzner, Süleyman Cenk Sahinalp, Elizabeth Sweedyk |
| 1999 | The Data Broadcast Problem with Non-Uniform Transmission Rimes. Claire Kenyon, Nicolas Schabanel |
| 1999 | The Full Degree Spanning Tree Problem. Randeep Bhatia, Samir Khuller, Robert Pless, Yoram J. Sussmann |
| 1999 | The Phase Transition in Random Horn Satisfiability and Its Algorithmic Implications. Gabriel Istrate |
| 1999 | Trade-offs Between Speed and Processor in Hard-Deadline Scheduling. Tak Wah Lam, Kar-Keung To |
| 1999 | Tree Pattern Matching and Subset Matching in Deterministic Richard Cole, Ramesh Hariharan, Piotr Indyk |
| 1999 | Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler. Michel X. Goemans, David P. Williamson |
| 1999 | Two-Point Euclidean Shortest Path Queries in the Plane. Yi-Jen Chiang, Joseph S. B. Mitchell |
| 1999 | Unscrambling Address Lines. Andrei Z. Broder, Michael Mitzenmacher, Laurent Moll |
| 1999 | Using Homogenous Weights for Approximating the Partial Cover Problem. Reuven Bar-Yehuda |
| 1999 | Using Stopping Times to Bound Mixing Times. Igor Pak |
| 1999 | Wavelength Conversion in Optical Networks. Jon M. Kleinberg, Amit Kumar |
| 1999 | What are the Least Tractable Instances of max Independent Set? David S. Johnson, Mario Szegedy |
| 1999 | When Does a Dynamic Programming Formulation Guarantee the Existence of an FPTAS? Gerhard J. Woeginger |