Clifford Stein

Industrial Engineering and Operations Research

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. 

  • 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
  • Association for Computing Machinery (ACM)
  • Institute for Operations Research and Management Science, (INFORMS)
  • Mathematical Programming Society (MPS)
  • 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
  • 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.