|Alma mater||Technion |
|Children||Amos and Naomi|
|Fields||Operations research, Mathematics|
|Thesis||Discrete Geometry, Group Representations and Combinatorial Optimization: an Interplay (1992)|
|Doctoral advisor||Louis J. Billera, Bernd Sturmfels, Leslie E. Trotter, Jr.|
Shmuel Onn (Hebrew: שמואל און; born 1960) is Professor of Operations Research and Dresner Chair at the The William Davidson Faculty of Industrial Engineering & Management|Faculty of Industrial Engineering & Management, Technion - Israel Institute of Technology.
Education and career
Shmuel Onn did his elementary education in Kadoorie(:he:בית הספר החקלאי כדורי). He received his B.Sc. (Cum Laude) in Electrical Engineering from Technion in 1980, and following his obligatory service in the Israeli Navy, received his M.Sc. from Technion in 1987. Onn obtained his Ph.D. in Operations Research from Cornell University, with minors in Applied Mathematics and Computer Science, in 1992. His thesis: Discrete Geometry, Group Representations and Combinatorial Optimization: an Interplay, was advised by Louis J. Billera, Bernd Sturmfels, and Leslie E. Trotter, Jr.
In 1994 Onn joined the Industrial Engineering and Management Faculty of Technion, where he is currently Professor and Dresner Chair. He was also a Visiting Professor and Nachdiplom Lecturer at the Institute for Mathematical Research, ETH Zürich in 2009, and Visiting Professor at the Mathematics Department in the University of California at Davis (2001-2002). Prof. Onn has been also a long-term visitor at various mathematical research institutes including Mittag-Leffler Institute in Stockholm, Mathematical Sciences Research Institute in Berkeley, California, and Mathematical Research Institute of Oberwolfach|Oberwolfach in Germany. He also served as Associate Editor for Mathematics of Operations Research in 2010–2016 and Associate Editor for Discrete Optimization in 2004–2010.
Onn advised several students and postdoctoral researchers who proceeded to pursue academic careers, including Antoine Deza, Sharon Aviran, Tal Raviv, Nir Halman, and Martin Koutecky.
Shmuel Onn is known for his contributions to integer programming and nonlinear combinatorial optimization. In particular, he developed an algorithmic theory of linear and nonlinear integer programming in variable dimension using Graver bases. This work introduced the theory of block-structured and n-fold integer programming, and the broader theory of sparse and bounded tree-depth integer programming, shown to be fixed-parameter tractable. These theories were followed up by other authors, and have applications in a variety of areas. 
Some other contributions of Onn include a framework that uses edge-directions for solving convex multi-criteria combinatorial optimization problems and its applications, a universality theorem showing that every integer program is one over slim three-dimensional tables, the settling of the complexity of hypergraph degree sequences, and the introduction of colorful linear programming.
Honors and awards
- 2010, Institute for Operations Research and the Management Sciences Computing Society (ICS) Prize.
- 2009, Nachdiplom Lecturer, Institute for Mathematical Research, ETH Zürich.
- Nonlinear discrete optimization. An algorithmic theory. Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), Zürich, 2010.
Onn is married to Ruth. They have two children, Amos and Naomi, and live in Haifa.
- Shmuel Onn - Overview, Technion
- Abridged CV, Technion
- Shmuel Onn, Mathematics Genealogy Project
- Past DIMACS Postdocs, Rutgers University
- Nachdiplom lectures - Past lectures, ETH
- Mathematics Colloquia and Seminars, University of California at Davis
- Personal Profile of Dr. Shmuel Onn, Mathematical Sciences Research Institute
- Research in Pairs - 2007 (PDF), Mathematical Research Institute of Oberwolfach
- MATHEMATICS OF OPERATIONS RESEARCH, INFORMS
- Students and Postdoctorants, Technion
- Shmuel Onn. Nonlinear discrete optimization. An algorithmic theory, European Mathematical Society, 2010
- Raymond Hemmecke; Shmuel Onn; Lyubov Romanchuk (2013). "N-fold integer programming in cubic time". Mathematical Programming (137): 325–341.
- Jesús A. De Loera; Raymond Hemmecke; Shmuel Onn; Robert Weismantel (2008). "N-fold integer programming". Discrete Optimization (5): 231–241.
- Martin Koutecky; Shmuel Onn (2021). "Sparse Integer Programming is FPT". Bulletin of the European Association for Theoretical Computer Science (134): 69–71.
- Friedrich Eisenbrand; Christoph Hunkenschroder; Kim-Manuel Klein; Martin Koutecky; Asaf Levin; Shmuel Onn (2019). "An algorithmic theory of integer programming" (PDF). arXiv.
- Martin Koutecky; Asaf Levin; Shmuel Onn (2018). "A parameterized strongly polynomial algorithm for block structured integer programs" (PDF). ICALP: 85:1–85:14.
- Jana Cslovjecsek; Friedrich Eisenbrand; Christoph Hunkenschroder; Kim-Manuel Klein; Lars Rohwedder; Robert Weismantel (2021). "Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time". Symposium on Discrete Algorithms: 1666–1681.
- Cornelius Brand; Martin Koutecký; Sebastian Ordyniak (2021). "Parameterized Algorithms for MILPs with Small Treedepth". AAAI: 12249–12257.
- Timothy F. N. Chan; Jacob W. Cooper; Martin Koutecký; Daniel Král'; Kristýna Pekárková (2020). "Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming" (PDF). ICALP: 26:1-26:19.
- Klaus Jansen; Alexandra Lassota; Lars Rohwedder (2019). "Near-Linear Time Algorithm for n-fold ILPs via Color Coding". ICALP: 75:1-75:13.
- Eduard Eiben; Robert Ganian; Dusan Knop; Kim-Manuel Klein; Sebastian Ordyniak; Michal Pilipczuk; Marcin Wrochna (2019). "Integer Programming and Incidence Treedepth" (PDF). IPCO: 194–204.
- Friedrich Eisenbrand; Christoph Hunkenschröder; Kim-Manuel Klein (2018). "Faster Algorithms for Integer Programs with Block Structure" (PDF). ICALP: 49:1-49:13.
- Dusan Knop; Martin Koutecký; Matthias Mnich (2020). "Voting and Bribing in Single-Exponential Time". ACM Transactions on Economics and Computation. 8 (3): 12:1-12:28.
- Robert Bredereck; Piotr Faliszewski; Rolf Niedermeier; Piotr Skowron; Nimrod Talmon (2020). "Mixed integer programming with convex/concave constraints: Fixed-parameter tractability and applications to multicovering and voting". Theoretical Computer Science (journal). 814: 86–105.
- Dusan Knop; Martin Koutecký; Matthias Mnich (2020). "Combinatorial n-fold integer programming and applications". Mathematical Programming. 184 (1): 1–34.
- Klaus Jansen; Kim-Manuel Klein; Marten Maack; Malin Rau (2019). "Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times". ITCS - Innovations in Theoretical Computer Science: 44:1-44:19.
- Dusan Knop; Martin Koutecký (2018). "Scheduling meets n-fold integer programming". Journal of Scheduling. 21 (5): 493–503.
- Lin Chen; Dániel Marx (2018). "Covering a tree with rooted subtrees - parameterized and approximation algorithms" (PDF). SODA: 2801–2820.
- Shmuel Onn; Uriel Rothblum (2004). "Convex combinatorial optimization" (PDF). Discrete & Computational Geometry. 32: 549–566.
- Eric Babson; Shmuel Onn; Rekha Thomas (2003). "The Hilbert zonotope and a polynomial time algorithm for universal Grobner bases". Advances in Applied Mathematics. 30: 529–544.
- Frank Hwang; Shmuel Onn; Uriel Rothblum (1999). "A polynomial time algorithm for shaped partition problems". SIAM Journal on Optimization. 10: 70–81.
- Jesus De Loera; Shmuel Onn (2006). "All linear and integer programs are slim 3-way transportation programs" (PDF). SIAM Journal on Optimization. 17: 806–821.
- Jesus De Loera; Shmuel Onn (2004). "The complexity of three-way statistical tables" (PDF). SIAM Journal on Computing. 33: 819–836.
- Antoine Deza; Asaf Levin; Syed M. Meesum; Shmuel Onn (2018). "Optimization over degree sequences". SIAM Journal on Discrete Mathematics. 32: 2067–2079.
- Imre Barany; Shmuel Onn (1997). "Colourful linear programming and its relatives" (PDF). Mathematics of Operations Research. 22: 550–567.
- Shmuel Onn - 2010 INFORMS Computing Society Prize, INFORMS