Jump to content

Shmuel Onn

Edit links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by OAbot (talk | contribs) at 11:40, 5 January 2024 (Open access bot: arxiv updated in citation with #oabot.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Shmuel Onn
Born1960
Israel
NationalityIsraeli
Alma materTechnion
Cornell University
SpouseRuth
ChildrenAmos and Naomi
Scientific career
FieldsOperations research, Mathematics
InstitutionsTechnion
Thesis Discrete Geometry, Group Representations and Combinatorial Optimization: an Interplay  (1992)
Doctoral advisorLouis J. Billera, Bernd Sturmfels, Leslie E. Trotter Jr.

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 elementary education in Kadoorie(he).[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. ^ a b c Shmuel Onn. Nonlinear discrete optimization: An algorithmic theory, European Mathematical Society, 2010
  3. ^ a b c d 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. ^ a b 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 (PDF), Mathematical Research Institute of Oberwolfach
  10. ^ "Editorial Board", Mathematics of Operations Research, 40 (4), INFORMS: c2–c3, 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. In Memory of George B. Dantzig. 5 (2): 231–241. 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 [math.OC].
  16. ^ Martin Koutecký; Asaf Levin; Shmuel Onn (2018). "A parameterized strongly polynomial algorithm for block structured integer programs" (PDF). ICALP. Leibniz International Proceedings in Informatics (LIPIcs). 107: 85:1–85:14. arXiv:1802.05859. doi:10.4230/LIPIcs.ICALP.2018.85. ISBN 9783959770767. S2CID 3336201.{{cite journal}}: CS1 maint: unflagged free DOI (link)
  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: 1666–1681. 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" (PDF). ICALP : 26:1–26:19. arXiv:1907.06688.
  20. ^ Klaus Jansen; Alexandra Lassota; Lars Rohwedder (2019). "Near-Linear Time Algorithm for n-fold ILPs via Color Coding". ICALP. Leibniz International Proceedings in Informatics (LIPIcs). 132: 75:1–75:13. doi:10.4230/LIPIcs.ICALP.2019.75. ISBN 9783959771092. S2CID 53300379.{{cite journal}}: CS1 maint: unflagged free DOI (link)
  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 (PDF). Lecture Notes in Computer Science. Vol. 11480. 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" (PDF). ICALP: 49:1–49:13. 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. 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. Leibniz International Proceedings in Informatics (LIPIcs). 124: 44:1–44:19. doi:10.4230/LIPIcs.ITCS.2019.44. ISBN 9783959770958. S2CID 24006600.{{cite journal}}: CS1 maint: unflagged free DOI (link)
  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" (PDF). SODA: 2801–2820.
  29. ^ Shmuel Onn; Uriel Rothblum (2004). "Convex combinatorial optimization" (PDF). 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" (PDF). 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" (PDF). 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" (PDF). Mathematics of Operations Research. 22 (3): 550–567. doi:10.1287/moor.22.3.550. Archived from the original (PDF) on 2021-11-25. Retrieved 2021-09-23.
  36. ^ Shmuel Onn - 2010 INFORMS Computing Society Prize, INFORMS
Retrieved from "https://en.wikipedia.org/w/index.php?title=Shmuel_Onn&oldid=1193745057"