Shmuel Onn Explained

Shmuel Onn
Birth Date:1960
Birth Place:Israel
Nationality:Israeli
Fields:Operations research, Mathematics
Workplaces:Technion
Alma Mater:Technion
Cornell University
Thesis Title:Discrete Geometry, Group Representations and Combinatorial Optimization: an Interplay
Thesis Year:1992
Doctoral Advisor:Louis J. Billera, Bernd Sturmfels, Leslie E. Trotter Jr.
Spouse:Ruth
Children:Amos and Naomi

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

Education

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 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.

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

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, and visiting professor at the Mathematics Department in the University of California at Davis (2001-2002). Professor Onn has been also a long-term visitor at various mathematical research institutes including Mittag-Leffler in Stockholm, MSRI in Berkeley, and 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 Koutecký.

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. This work introduced the theory of block-structured and n-fold integer programming,[1] [2] and the broader theory of sparse and bounded tree-depth integer programming, shown to be fixed-parameter tractable.[3] [4] [5] These theories were followed up by other authors,[6] [7] [8] [9] [10] [11] and have applications in a variety of areas.[12] [13] [14] [15] [16] [17]

Some other contributions of Onn include a framework that uses edge-directions for solvingconvex multi-criteria combinatorial optimization problems and its applications,[18] [19] [20] a universality theorem showing that every integer program is one over slim three-dimensional tables,[21] [22] the settling of the complexity of hypergraph degree sequences,[23] and the introduction of colorful linear programming.[24]

Honors and awards

Books

Personal life

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

External links

Notes and References

  1. Raymond Hemmecke. Shmuel Onn. Lyubov Romanchuk. N-fold integer programming in cubic time. Mathematical Programming. 2013. 137. 325–341. 1–2. 10.1007/s10107-011-0490-y. 1101.3267. 964450.
  2. Jesus De Loera. Raymond Hemmecke. Shmuel Onn. Robert Weismantel. N-fold integer programming. Discrete Optimization. In Memory of George B. Dantzig. 2008. 5. 231–241. 2. 10.1016/j.disopt.2006.06.006. 997926. free.
  3. Martin Koutecký. Shmuel Onn. Sparse Integer Programming is FPT. Bulletin of the European Association for Theoretical Computer Science. 2021. 2. 69–71. 134.
  4. Friedrich Eisenbrand. Christoph Hunkenschroder. Kim-Manuel Klein. Martin Koutecký. Asaf Levin. Shmuel Onn. An algorithmic theory of integer programming. 2019. math.OC. 1904.01361.
  5. Martin Koutecký. Asaf Levin. Shmuel Onn. A parameterized strongly polynomial algorithm for block structured integer programs. ICALP. Leibniz International Proceedings in Informatics (LIPIcs). 2018. 107. 85:1–85:14. 10.4230/LIPIcs.ICALP.2018.85. free . 1802.05859. 9783959770767. 3336201.
  6. Jana Cslovjecsek. Friedrich Eisenbrand. Christoph Hunkenschroder. Kim-Manuel Klein. Lars Rohwedder. Robert Weismantel. Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time. SODA. 2021. 1666–1681. 2002.07745.
  7. Cornelius Brand. Martin Koutecký. Sebastian Ordyniak. Parameterized Algorithms for MILPs with Small Treedepth. AAAI. 2021. 35. 14. 12249–12257. 10.1609/aaai.v35i14.17454 . 1912.03501. 208909901 .
  8. Timothy F. N. Chan. Jacob W. Cooper. Martin Koutecký. Daniel Král'. Kristýna Pekárková. Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming. ICALP . 2020. 26:1–26:19. 1907.06688.
  9. Klaus Jansen. Alexandra Lassota. Lars Rohwedder. Near-Linear Time Algorithm for n-fold ILPs via Color Coding. ICALP. Leibniz International Proceedings in Informatics (LIPIcs). 2019. 132. 75:1–75:13. 10.4230/LIPIcs.ICALP.2019.75. free . 9783959771092. 53300379.
  10. Book: Eduard Eiben. Robert Ganian. Dusan Knop. Kim-Manuel Klein. Sebastian Ordyniak. Michal Pilipczuk. Marcin Wrochna. Integer Programming and Combinatorial Optimization. Integer Programming and Incidence Treedepth . Lecture Notes in Computer Science. 2019. 11480. 194–204. 2012.00079. 10.1007/978-3-030-17953-3_15 . 978-3-030-17953-3. 142503705.
  11. Friedrich Eisenbrand. Christoph Hunkenschröder. Kim-Manuel Klein. Faster Algorithms for Integer Programs with Block Structure. ICALP. 2018. 49:1–49:13. 1802.06289.
  12. Dusan Knop. Martin Koutecký. Matthias Mnich. Voting and Bribing in Single-Exponential Time. ACM Transactions on Economics and Computation. 2020. 8. 3. 12:1–12:28. 10.1145/3396855. 218529858. free. 1812.01852.
  13. Robert Bredereck. Piotr Faliszewski. Rolf Niedermeier. Piotr Skowron. Nimrod Talmon. Rolf Niedermeier. Mixed integer programming with convex/concave constraints: Fixed-parameter tractability and applications to multicovering and voting. Theoretical Computer Science. 2020. 814. 86–105. 10.1016/j.tcs.2020.01.017. 1709.02850. 3227033.
  14. Dusan Knop. Martin Koutecký. Matthias Mnich. Combinatorial n-fold integer programming and applications. Mathematical Programming. 2020. 184. 1. 1–34. 10.1007/s10107-019-01402-2. 213316783. 1705.08657.
  15. Klaus Jansen. Kim-Manuel Klein. Marten Maack. Malin Rau. Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times. ITCS - Innovations in Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs). 2019. 124. 44:1–44:19. 10.4230/LIPIcs.ITCS.2019.44. free . 9783959770958. 24006600.
  16. Dusan Knop. Martin Koutecký. Scheduling meets n-fold integer programming. Journal of Scheduling. 2018. 21. 5. 493–503. 10.1007/s10951-017-0550-0. 1603.02611. 9627563.
  17. Lin Chen. Dániel Marx. Covering a tree with rooted subtrees - parameterized and approximation algorithms. SODA. 2018. 2801–2820.
  18. Shmuel Onn. Uriel Rothblum. Convex combinatorial optimization. Discrete & Computational Geometry. 2004. 32. 4. 549–566. 10.1007/s00454-004-1138-y. 803661.
  19. Eric Babson. Shmuel Onn. Rekha Thomas. The Hilbert zonotope and a polynomial time algorithm for universal Grobner bases. Advances in Applied Mathematics. 2003. 30. 3. 529–544. 10.1016/S0196-8858(02)00509-2. 7178467. free. math/0207135.
  20. Frank Hwang. Shmuel Onn. Uriel Rothblum. A polynomial time algorithm for shaped partition problems. SIAM Journal on Optimization. 1999. 10. 70–81. 10.1137/S1052623497344002.
  21. Jesus De Loera. Shmuel Onn. All linear and integer programs are slim 3-way transportation programs. SIAM Journal on Optimization. 2006. 17. 3. 806–821. 10.1137/040610623.
  22. Jesus De Loera. Shmuel Onn. The complexity of three-way statistical tables. SIAM Journal on Computing. 2004. 33. 4. 819–836. 10.1137/S0097539702403803. math/0207200. 14941545.
  23. Antoine Deza. Asaf Levin. Syed M. Meesum. Shmuel Onn. Optimization over degree sequences. SIAM Journal on Discrete Mathematics. 2018. 32. 3. 2067–2079. 10.1137/17M1134482. 1706.03951. 52039639.
  24. Imre Bárány. Shmuel Onn. Colourful linear programming and its relatives. Mathematics of Operations Research. 1997. 22. 3. 550–567. 10.1287/moor.22.3.550. 2021-09-23. 2021-11-25. https://web.archive.org/web/20211125154005/https://ie.technion.ac.il/~onn/Selected/MOR97.pdf. dead.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Shmuel Onn".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.