Éva Tardos and David Shmoys won a 30-year Test of Time Award at the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021) for their paper, written with Serge Plotkin, "Fast Approximation Algorithms for Fractional Packing and Covering Problems" (1991).
Tardos is the Jacob Gould Schurman Professor of Computer Science and Chair of the Department of Computer Science in the Cornell Ann S. Bowers College of Computing and Information Science and Shmoys is Laibe/Acheson Professor of Business Management and Leadership Studies in the School of Operations Research and Information Engineering, a member of the Department of Computer Science, and director of the Center for Data Science for Enterprise and Society.
In the paper, the authors present fast algorithms that find approximate solutions for a general class of problems, which are called fractional packing and covering problems. In mathematics, packing problems present a challenge to optimization. In trying to increase optimization by means of fast algorithms, the goal is to pack objects together into containers such that either (1) a single container is packed as densely as possible or (2) all objects are accounted for using the fewest containers. Each packing problem has a tandem covering problem, which involves determining how many objects are required to completely fill a container.
The only previously known algorithms for solving these problems are based on general linear programming techniques, write the authors in their assessment of the field. The techniques developed in this paper greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions for multicommodity flow.
The paper, which was originally published in the Proceedings of the Annual IEEE Symposium on Foundations of Computer Science, continues to influence the field of algorithm research. The authors' approach yields several orders of magnitude of improvement over the best previously known running times for the scheduling of unrelated parallel machines in both the preemptive and the non-preemptive models, for the job shop problem, for the cutting-stock problem, and for the minimum-cost multicommodity flow problem. This award-winning paper has transformed approaches to these three optimization problems by providing solutions that enhance computational efficiencies, especially processing optimization.
Read further coverage of these faculty:
Éva Tardos named to the American Philosophical Society
David Shmoys part of New Center that will Foster Data Science Research