stringtranslate.com

Shmuel Onn

Shmuel Onn (hebreo: שמואל און; nacido en 1960) es un matemático , profesor de Investigación de Operaciones y Cátedra Dresner en el Technion - Instituto de Tecnología de Israel . [1] Es conocido por sus contribuciones a la programación entera y la optimización combinatoria no lineal . [2]

Educación

Shmuel Onn hizo su educación primaria en Kadoorie (él). [3] Recibió su B.Sc. (Cum Laude) en Ingeniería Eléctrica del Technion en 1980, y luego de su servicio obligatorio en la Marina , recibió su M.Sc. de Technion en 1987. [3] Onn obtuvo su doctorado. en investigación de operaciones de la Universidad de Cornell , con especialización en matemáticas aplicadas e informática , en 1992. Su tesis, "Geometría discreta, representaciones de grupos y optimización combinatoria: una interacción", fue asesorada por Louis J. Billera , Bernd Sturmfels y Leslie E. Trotón Jr. [4]

Durante 1992-1993 fue becario postdoctoral en DIMACS , [5] y durante 1993-1994 fue becario postdoctoral Alexander von Humboldt en la Universidad de Passau , Alemania . [3]

Carrera

En 1994 Onn se incorporó a la Facultad de Ciencias de la Decisión y los Datos de Technion, donde actualmente es profesor y catedrático Dresner. También fue profesor visitante y profesor Nachdiplom en el Instituto de Investigación Matemática , ETH Zürich en 2009, [6] y profesor invitado en el Departamento de Matemáticas de la Universidad de California en Davis (2001-2002). [7] El profesor Onn también ha sido visitante de larga duración en varios institutos de investigación matemática, incluidos Mittag-Leffler en Estocolmo , MSRI en Berkeley , [8] y Oberwolfach en Alemania. [9] También se desempeñó como editor asociado de Matemáticas de investigación de operaciones en 2010-2016 [10] y editor asociado de optimización discreta en 2004-2010. [3]

Onn asesoró a varios estudiantes e investigadores postdoctorales que procedieron a seguir carreras académicas, incluidos Antoine Deza, Sharon Aviran, Tal Raviv, Nir Halman y Martin Koutecký. [11]

Investigación

Shmuel Onn es conocido por sus contribuciones a la programación entera y la optimización combinatoria no lineal . En particular, desarrolló una teoría algorítmica de programación entera lineal y no lineal en dimensión variable utilizando bases de Graver . [2] Este trabajo introdujo la teoría de la programación entera estructurada en bloques y n veces, [12] [13] y la teoría más amplia de la programación entera de profundidad de árbol limitada y dispersa, que se ha demostrado que es manejable con parámetros fijos. [14] [15] [16] Estas teorías fueron seguidas por otros autores, [17] [18] [19] [20] [21] [22] y tienen aplicaciones en una variedad de áreas. [23] [24] [25] [26] [27] [28]

Algunas otras contribuciones de Onn incluyen un marco que utiliza direcciones de borde para resolver problemas de optimización combinatoria convexa de criterios múltiples y sus aplicaciones, [29] [30] [31] un teorema de universalidad que muestra que cada programa entero es uno sobre delgado tridimensional tablas, [32] [33] la solución de la complejidad de las secuencias de grados de hipergrafo, [34] y la introducción de una colorida programación lineal. [35]

Honores y premios

Libros

Vida personal

Shmuel está casado con Rut. Tienen dos hijos, Amos y Naomi, y viven en Haifa .

enlaces externos

Referencias

  1. ^ Shmuel Onn, Technion
  2. ^ a b C Shmuel Onn. Optimización discreta no lineal: una teoría algorítmica, Sociedad Matemática Europea, 2010
  3. ^ abcd CV abreviado, Technion, archivado desde el original el 25 de noviembre de 2021 , consultado el 30 de septiembre de 2021
  4. ^ Shmuel Onn, Proyecto de genealogía de matemáticas
  5. ^ Postdoctorados anteriores de DIMACS, Universidad de Rutgers
  6. ^ conferencias ab Nachdiplom - Conferencias anteriores, ETH
  7. ^ Coloquios y seminarios de matemáticas, Universidad de California en Davis
  8. ^ Perfil personal del Dr. Shmuel Onn, Instituto de Investigación en Ciencias Matemáticas
  9. ^ Investigación por parejas - 2007 (PDF) , Instituto de Investigación Matemática de Oberwolfach
  10. ^ "Consejo Editorial", Matemáticas de la Investigación Operativa , 40 (4), INFORMA: c2–c3, 2015, doi : 10.1287/moor.2015.eb.v404
  11. ^ Estudiantes y posdoctorantes, Technion, archivado desde el original el 25 de noviembre de 2021 , consultado el 30 de septiembre de 2021.
  12. ^ Raymond Hemmecke; Shmuel Onn; Amor Romanchuk (2013). "Programación de números enteros N veces en tiempo cúbico". Programación Matemática . 137 (1–2): 325–341. arXiv : 1101.3267 . doi :10.1007/s10107-011-0490-y. S2CID  964450.
  13. ^ Jesús De Loera ; Raymond Hemmecke; Shmuel Onn; Robert Weismantel (2008). "Programación de números enteros N veces". Optimización discreta . En memoria de George B. Dantzig. 5 (2): 231–241. doi : 10.1016/j.disopt.2006.06.006 . S2CID  997926.
  14. ^ Martín Koutecký; Shmuel Onn (2021). "La programación entera dispersa es FPT". Boletín de la Asociación Europea de Informática Teórica . 2 (134): 69–71.
  15. ^ Federico Eisenbrand ; Christoph Hunkenschröder; Kim-Manuel Klein; Martín Koutecký; Asaf Levin; Shmuel Onn (2019). "Una teoría algorítmica de la programación entera". arXiv : 1904.01361 [matemáticas.OC].
  16. ^ Martín Koutecký; Asaf Levin; Shmuel Onn (2018). "Un algoritmo fuertemente polinómico parametrizado para programas enteros estructurados en bloques" (PDF) . ICALP . Procedimientos internacionales de informática de Leibniz (LIPIcs). 107 : 85:1–85:14. arXiv : 1802.05859 . doi : 10.4230/LIPIcs.ICALP.2018.85 . ISBN 9783959770767. S2CID  3336201.
  17. ^ Jana Cslovjecsek; Federico Eisenbrand; Christoph Hunkenschröder; Kim-Manuel Klein; Lars Rohwedder; Robert Weismantel (2021). "Programación lineal y entera estructurada en bloques en tiempo fuertemente polinomial y casi lineal". Refresco : 1666–1681. arXiv : 2002.07745 .
  18. ^ Marca Cornelio; Martín Koutecký; Sebastián Ordyniak (2021). "Algoritmos parametrizados para MILP con profundidad de árbol pequeña". AAAI . 35 (14): 12249–12257. arXiv : 1912.03501 . doi : 10.1609/aaai.v35i14.17454. S2CID  208909901.
  19. ^ Timoteo FN Chan; Jacob W. Cooper; Martín Koutecký; Daniel Král'; Kristýna Pekárková (2020). "Matrices de algoritmo parametrizado óptimo de profundidad de árbol y de fila invariante para programación entera" (PDF) . ICALP : 26:1–26:19. arXiv : 1907.06688 .
  20. ^ Klaus Jansen; Alexandra Lassota; Lars Rohwedder (2019). "Algoritmo de tiempo casi lineal para ILP n veces mediante codificación de colores". ICALP . Procedimientos internacionales de informática de Leibniz (LIPIcs). 132 : 75:1–75:13. doi : 10.4230/LIPIcs.ICALP.2019.75 . ISBN 9783959771092. S2CID  53300379.
  21. ^ Eduard Eiben; Robert Ganian; Dusan Knop; Kim-Manuel Klein; Sebastián Ordyniak; Michal Pilipczuk; Marcin Wrochna (2019). "Programación entera y profundidad del árbol de incidencia". Programación entera y optimización combinatoria (PDF) . Apuntes de conferencias sobre informática. vol. 11480. págs. 194-204. arXiv : 2012.00079 . doi :10.1007/978-3-030-17953-3_15. ISBN 978-3-030-17953-3. S2CID  142503705.
  22. ^ Federico Eisenbrand; Christoph Hunkenschröder; Kim-Manuel Klein (2018). "Algoritmos más rápidos para programas enteros con estructura de bloques" (PDF) . ICALP : 49:1–49:13. arXiv : 1802.06289 .
  23. ^ Dusan Knop; Martín Koutecký; Matías Mnich (2020). "Votar y sobornar en tiempo exponencial único". Transacciones ACM sobre Economía y Computación . 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 Talmón (2020). "Programación de enteros mixtos con restricciones convexas/cóncavas: trazabilidad de parámetros fijos y aplicaciones a multicobertura y votación". Informática Teórica . 814 : 86-105. arXiv : 1709.02850 . doi : 10.1016/j.tcs.2020.01.017. S2CID  3227033.
  25. ^ Dusan Knop; Martín Koutecký; Matías Mnich (2020). "Aplicaciones y programación combinatoria de enteros n veces". Programación Matemática . 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). "Potenciación de la IP de configuración: nuevos resultados de PTAS para la programación con tiempos de configuración". ITCS - Innovaciones en Informática Teórica . Procedimientos internacionales de informática de Leibniz (LIPIcs). 124 : 44:1–44:19. doi : 10.4230/LIPIcs.ITCS.2019.44 . ISBN 9783959770958. S2CID  24006600.
  27. ^ Dusan Knop; Martín Koutecký (2018). "La programación se combina con la programación de números enteros n". Diario de programación . 21 (5): 493–503. arXiv : 1603.02611 . doi :10.1007/s10951-017-0550-0. S2CID  9627563.
  28. ^ Lin Chen; Daniel Marx (2018). "Cubrir un árbol con subárboles enraizados: algoritmos de aproximación y parametrizados" (PDF) . Refresco : 2801–2820.
  29. ^ Shmuel Onn; Uriel Rothblum (2004). "Optimización combinatoria convexa" (PDF) . Geometría discreta y computacional . 32 (4): 549–566. doi :10.1007/s00454-004-1138-y. S2CID  803661.
  30. ^ Eric Babson; Shmuel Onn; Rekha Thomas (2003). "El zonotopo de Hilbert y un algoritmo de tiempo polinómico para bases universales de Grobner". Avances en Matemática Aplicada . 30 (3): 529–544. arXiv : matemáticas/0207135 . doi : 10.1016/S0196-8858(02)00509-2 . S2CID  7178467.
  31. ^ Frank Hwang; Shmuel Onn; Uriel Rothblum (1999). "Un algoritmo de tiempo polinomial para problemas de partición conformada". Revista SIAM sobre Optimización . 10 : 70–81. doi :10.1137/S1052623497344002.
  32. ^ Jesús De Loera; Shmuel Onn (2006). "Todos los programas lineales y enteros son programas de transporte delgados de 3 vías" (PDF) . Revista SIAM sobre Optimización . 17 (3): 806–821. doi :10.1137/040610623.
  33. ^ Jesús De Loera; Shmuel Onn (2004). "La complejidad de las tablas estadísticas de tres factores" (PDF) . Revista SIAM de Computación . 33 (4): 819–836. arXiv : matemáticas/0207200 . doi :10.1137/S0097539702403803. S2CID  14941545.
  34. ^ Antonio Deza; Asaf Levin; Syed M. Meesum; Shmuel Onn (2018). "Optimización sobre secuencias de grados". Revista SIAM de Matemática Discreta . 32 (3): 2067–2079. arXiv : 1706.03951 . doi :10.1137/17M1134482. S2CID  52039639.
  35. ^ Imre Bárány ; Shmuel Onn (1997). "Programación lineal colorida y sus parientes" (PDF) . Matemáticas de la Investigación de Operaciones . 22 (3): 550–567. doi :10.1287/moor.22.3.550. Archivado desde el original (PDF) el 25 de noviembre de 2021 . Consultado el 23 de septiembre de 2021 .
  36. ^ Shmuel Onn - Premio INFORMS Computing Society 2010, INFORMS