Clifford Stein

PROFESSOR OF INDUSTRIAL ENGINEERING AND OPERATIONS RESEARCH PROFESSOR OF COMPUTER SCIENCE MEMBER, DATA SCIENCE INSTITUTE

424 S.W. Mudd 
Mail Code 4704

Tel(212) 854-5238
Fax(212) 854-8103

Clifford Stein conducts research in the design and analysis of efficient algorithms and in combinatorial optimization.  He is particularly interested in the design of algorithms for hard-to-solve problems, arising in areas such as network design and scheduling. He designs algorithms for a variety of applications ranging from scheduling problems that arise in computer systems to problems that arise in industrial manufacturing facilities.  His research includes both the rigorous mathematical analysis of algorithms and the algorithm engineering needed to design efficient implementations.  He is particularly interested in the algorithmic issues involved in energy usage, such as managing the work in a data center in an energy efficient manner.   He is also the co-author of the popular textbook, Introduction to Algorithms, which has sold over 500,000 copies and been translated into more than a dozen languages. 

Research Interests

Design and analysis of algorithms, combinatorial optimization, operations research, network algorithms, scheduling, algorithm engineering and internet

Stein is particularly interested in the design of approximation algorithms for NP-hard problems and on designing online algorithms, which handle the case when the necessary data arrives over time.  His work has included many advances in the field of scheduling, which considers the allocation of resources over time, and in network and graph algorithms. 

Stein received a BSE in Computer Science from Princeton University in 1987 and a PhD in Computer Science from the Massachusetts Institute of Technology in 1992.   He is a fellow of the Association for Computing Machinery, chair of the Steering Committee for the Annual Symposium on Discrete Algorithms, and has received a Career grant and a Sloan Fellowship.

PROFESSIONAL EXPERIENCE

  • Chair of Industrial Engineering and Operations Research, Columbia University, 2008-2013
  • Professor of Industrial Engineering and Operations Research, Columbia University, 2001-
  • Professor of Computer Science, Columbia University, 2001-
  • Assistant and Associate Professor of Computer Science, Dartmouth College, 1992-2001

PROFESSIONAL AFFILIATIONS

  • Association for Computing Machinery (ACM)
  • Institute for Operations Research and Management Science, (INFORMS)
  • Mathematical Programming Society (MPS)

HONORS & AWARDS

  • Best Paper Award, ICALP, 2015
  • Fellow, ACM, 2012
  • Sloan Research Fellow, 1999
  • Karen Wetterhahn Award for Distinguished Creative or Scholarly Achievement, 1998
  • NSF Career Award, 1996

SELECTED PUBLICATIONS

  • Faster Fully Dynamic Matching with Small Approximation Ratios, with Aaron Bernstein.  In Symposium on Discrete Algorithms (SODA), 2016.
  • Minimizing the total weighted completion time of coflows in datacenter networks, with Zhen Qiu and Yuan Zhong, In Symposium on Parallel Algorithms and Architectures (SPAA), 2015.
  • A Fast Distributed Stateless Algorithm for Alpha-Fair Packing, with J. Marasevic and G. Zussman, In International Conference on Automata, Languages and Programming (ICALP), 2015.
  • Maintaining assignments online: Matching, scheduling and flows, with Anupam Gupta and Amit Kumar, In Symposium on Discrete Algorithms (SODA), 2014.
  • Hallucination Helps: Energy efficient virtual circuit routing, with Antonios Antoniadis, Sunjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, In Symposium on Discrete Algorithms (SODA), 2014.
  • Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing, with Ravishankar Krishnaswamy, Viswanath Nagarajan, and Kirk Pruhs. In Symposium on Theory of Computing (STOC), 2014.
  • A Convex Alternative to the IBM 2 Model, with Michael Collins and Andre Simion, Conference on Empirical Methods in Natural Language Processing (EMNLP), 2013.
  • Online Stochastic Packing Applied to Display Ad Allocations. with Jon Feldman, Monika Henzinger, Nitish Korula, and Vahab S. Mirrokni. In Proceedings of European Symposium on Algorithms (ESA). 2010: 182-194. 2010
  • Non-Preemptive Min-Sum Scheduling with Resource Augmentation, with N. Bansal, H. Chan, R. Kandekar, K. Pruhs, and B. Schieber. In  IEEE Symposium on the Foundations of Computer Science (FOCS), 2007
  • A New Approach to the Minimum Cut Problem, with D. Karger. In Journal of the ACM, 43:4, pp. 601–640, July, 1996.