Shmuel Onn
Native nameשמואל און
Birth date1960
Birth placeIsrael
FieldsOperations research, Mathematics
WorkplacesTechnion
Alma materTechnion
Cornell University
Thesis year1992
Doctoral advisorLouis J. Billera, Bernd Sturmfels, Leslie E. Trotter Jr.
SpouseRuth

Shmuel Onn (Hebrew: שמואל און; born 1960) is a mathematician, Professor of Operations Research and Dresner Chair at the Technion - Israel Institute of Technology.[1] He is known for his contributions to integer programming and nonlinear combinatorial optimization.[2]

Education

Shmuel Onn did his high school education in Kadoorie Agricultural High School.[3] He received his B.Sc. (Cum Laude) in Electrical Engineering from Technion in 1980, and following his obligatory service in the Navy, received his M.Sc. from Technion in 1987.[3] 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.[4]

During 1992–1993 he was a postdoctoral fellow at DIMACS,[5] and during 1993-1994 he was an Alexander von Humboldt postdoctoral fellow at the University of Passau, Germany.[3]

Career

In 1994 Onn joined the Faculty of Data and Decision Sciences 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,[6] and visiting professor at the Mathematics Department in the University of California at Davis (2001-2002).[7] Professor Onn has been also a long-term visitor at various mathematical research institutes including Mittag-Leffler in Stockholm, MSRI in Berkeley,[8] and Oberwolfach in Germany.[9] He also served as Associate Editor for Mathematics of Operations Research in 2010–2016[10] and Associate Editor for Discrete Optimization in 2004–2010.[3]

Onn advised several students and postdoctoral researchers who proceeded to pursue academic careers, including Antoine Deza, Sharon Aviran, Tal Raviv, Nir Halman, and Martin Koutecký.[11]

Research

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.[2] This work introduced the theory of block-structured and n-fold integer programming,[12][13] and the broader theory of sparse and bounded tree-depth integer programming, shown to be fixed-parameter tractable.[14][15][16] These theories were followed up by other authors,[17][18][19][20][21][22] and have applications in a variety of areas.[23] [24][25][26][27][28]

Some other contributions of Onn include a framework that uses edge-directions for solving convex multi-criteria combinatorial optimization problems and its applications,[29][30][31] a universality theorem showing that every integer program is one over slim three-dimensional tables,[32][33] the settling of the complexity of hypergraph degree sequences,[34] and the introduction of colorful linear programming.[35]

Honors and awards

Books

Personal life

Shmuel is married to Ruth. They have two children, Amos and Naomi, and live in Haifa.

References

  1. ^ "Shmuel Onn", Technion
  2. ^ "Shmuel Onn. Nonlinear discrete optimization: An algorithmic theory", European Mathematical Society, 2010
  3. ^ "Abridged CV", Technion, archived from the original on 2021-11-25, retrieved 2021-09-30
  4. ^ "Shmuel Onn", Mathematics Genealogy Project
  5. ^ "Past DIMACS Postdocs", Rutgers University
  6. ^ "Nachdiplom lectures - Past lectures", ETH
  7. ^ "Mathematics Colloquia and Seminars", University of California at Davis
  8. ^ "Personal Profile of Dr. Shmuel Onn", Mathematical Sciences Research Institute
  9. ^ "Research in Pairs - 2007", Mathematical Research Institute of Oberwolfach
  10. ^ "Editorial Board", Mathematics of Operations Research. 40 (4): c2–c3, INFORMS, 2015, doi:10.1287/moor.2015.eb.v404
  11. ^ "Students and Postdoctorants", Technion, archived from the original on 2021-11-25, retrieved 2021-09-30
  12. ^ Raymond Hemmecke; Shmuel Onn; Lyubov Romanchuk (2013). "N-fold integer programming in cubic time". Mathematical Programming. 137 (1–2): 325–341. arXiv:1101.3267. doi:10.1007/s10107-011-0490-y. S2CID 964450
  13. ^ Jesus De Loera; Raymond Hemmecke; Shmuel Onn; Robert Weismantel (2008). "N-fold integer programming". Discrete Optimization. 5 (2): 231–241. In Memory of George B. Dantzig. doi:10.1016/j.disopt.2006.06.006. S2CID 997926
  14. ^ Martin Koutecký & Shmuel Onn (2021). "Sparse Integer Programming is FPT". Bulletin of the European Association for Theoretical Computer Science. 2 (134): 69–71.
  15. ^ Friedrich Eisenbrand; Christoph Hunkenschroder; Kim-Manuel Klein; Martin Koutecký; Asaf Levin; Shmuel Onn (2019). "An algorithmic theory of integer programming". arXiv:1904.01361
  16. ^ Martin Koutecký; Asaf Levin; Shmuel Onn (2018). "A parameterized strongly polynomial algorithm for block structured integer programs". ICALP. 107: 85:1–85:14. Leibniz International Proceedings in Informatics (LIPIcs). arXiv:1802.05859. doi:10.4230/LIPIcs.ICALP.2018.85. ISBN 9783959770767. S2CID 3336201
  17. ^ 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". SODA. arXiv:2002.07745
  18. ^ Cornelius Brand; Martin Koutecký; Sebastian Ordyniak (2021). "Parameterized Algorithms for MILPs with Small Treedepth". AAAI. 35 (14): 12249–12257. arXiv:1912.03501. doi:10.1609/aaai.v35i14.17454. S2CID 208909901
  19. ^ 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". ICALP. arXiv:1907.06688
  20. ^ Klaus Jansen; Alexandra Lassota; Lars Rohwedder (2019). "Near-Linear Time Algorithm for n-fold ILPs via Color Coding". ICALP. 132: 75:1–75:13. Leibniz International Proceedings in Informatics (LIPIcs). doi:10.4230/LIPIcs.ICALP.2019.75. ISBN 9783959771092. S2CID 53300379
  21. ^ Eduard Eiben; Robert Ganian; Dusan Knop; Kim-Manuel Klein; Sebastian Ordyniak; Michal Pilipczuk; Marcin Wrochna (2019). "Integer Programming and Incidence Treedepth". Integer Programming and Combinatorial Optimization. Vol. 11480. Lecture Notes in Computer Science. pp. 194–204. arXiv:2012.00079. doi:10.1007/978-3-030-17953-3_15. ISBN 978-3-030-17953-3. S2CID 142503705
  22. ^ Friedrich Eisenbrand; Christoph Hunkenschröder; Kim-Manuel Klein (2018). "Faster Algorithms for Integer Programs with Block Structure". ICALP. arXiv:1802.06289
  23. ^ 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. arXiv:1812.01852. doi:10.1145/3396855. S2CID 218529858
  24. ^ 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. 814: 86–105. arXiv:1709.02850. doi:10.1016/j.tcs.2020.01.017. S2CID 3227033
  25. ^ Dusan Knop; Martin Koutecký; Matthias Mnich (2020). "Combinatorial n-fold integer programming and applications". Mathematical Programming. 184 (1): 1–34. arXiv:1705.08657. doi:10.1007/s10107-019-01402-2. hdl:11420/4607. S2CID 213316783
  26. ^ 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. 124: 44:1–44:19. Leibniz International Proceedings in Informatics (LIPIcs). doi:10.4230/LIPIcs.ITCS.2019.44. ISBN 9783959770958. S2CID 24006600
  27. ^ Dusan Knop & Martin Koutecký (2018). "Scheduling meets n-fold integer programming". Journal of Scheduling. 21 (5): 493–503. arXiv:1603.02611. doi:10.1007/s10951-017-0550-0. S2CID 9627563
  28. ^ Lin Chen & Dániel Marx (2018). "Covering a tree with rooted subtrees - parameterized and approximation algorithms". SODA
  29. ^ Shmuel Onn & Uriel Rothblum (2004). "Convex combinatorial optimization". Discrete & Computational Geometry. 32 (4): 549–566. doi:10.1007/s00454-004-1138-y. S2CID 803661
  30. ^ Eric Babson; Shmuel Onn; Rekha Thomas (2003). "The Hilbert zonotope and a polynomial time algorithm for universal Grobner bases". Advances in Applied Mathematics. 30 (3): 529–544. arXiv:math/0207135. doi:10.1016/S0196-8858(02)00509-2. S2CID 7178467
  31. ^ Frank Hwang; Shmuel Onn; Uriel Rothblum (1999). "A polynomial time algorithm for shaped partition problems". SIAM Journal on Optimization. 10: 70–81. doi:10.1137/S1052623497344002
  32. ^ Jesus De Loera & Shmuel Onn (2006). "All linear and integer programs are slim 3-way transportation programs". SIAM Journal on Optimization. 17 (3): 806–821. doi:10.1137/040610623
  33. ^ Jesus De Loera & Shmuel Onn (2004). "The complexity of three-way statistical tables". SIAM Journal on Computing. 33 (4): 819–836. arXiv:math/0207200. doi:10.1137/S0097539702403803. S2CID 14941545
  34. ^ Antoine Deza; Asaf Levin; Syed M. Meesum; Shmuel Onn (2018). "Optimization over degree sequences". SIAM Journal on Discrete Mathematics. 32 (3): 2067–2079. arXiv:1706.03951. doi:10.1137/17M1134482. S2CID 52039639
  35. ^ Imre Bárány & Shmuel Onn (1997). "Colourful linear programming and its relatives". Mathematics of Operations Research. 22 (3): 550–567. doi:10.1287/moor.22.3.550. Archived from the original on 2021-11-25. Retrieved 2021-09-23.
  36. ^ "Shmuel Onn - 2010 INFORMS Computing Society Prize", INFORMS