matemático israelí
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
- 2010, Premio INFORMS Computing Society (ICS). [36]
- 2009, Profesor Nachdiplom, Instituto de Investigación Matemática, ETH Zürich. [6]
Libros
- Optimización discreta no lineal: una teoría algorítmica. Conferencias de Zurich sobre Matemáticas Avanzadas. Sociedad Europea de Matemáticas (EMS), Zúrich, 2010. [2]
Vida personal
Shmuel está casado con Rut. Tienen dos hijos, Amos y Naomi, y viven en Haifa .
enlaces externos
- Shmuel Onn (página personal) Archivado el 2 de julio de 2020 en Wayback Machine , Technion
- Shmuel Onn, Technion
- Serie de videoconferencias sobre optimización discreta no lineal en MSRI, Berkeley
Referencias
- ^ Shmuel Onn, Technion
- ^ a b C Shmuel Onn. Optimización discreta no lineal: una teoría algorítmica, Sociedad Matemática Europea, 2010
- ^ abcd CV abreviado, Technion, archivado desde el original el 25 de noviembre de 2021 , consultado el 30 de septiembre de 2021
- ^ Shmuel Onn, Proyecto de genealogía de matemáticas
- ^ Postdoctorados anteriores de DIMACS, Universidad de Rutgers
- ^ conferencias ab Nachdiplom - Conferencias anteriores, ETH
- ^ Coloquios y seminarios de matemáticas, Universidad de California en Davis
- ^ Perfil personal del Dr. Shmuel Onn, Instituto de Investigación en Ciencias Matemáticas
- ^ Investigación por parejas - 2007 (PDF) , Instituto de Investigación Matemática de Oberwolfach
- ^ "Consejo Editorial", Matemáticas de la Investigación Operativa , 40 (4), INFORMA: c2–c3, 2015, doi : 10.1287/moor.2015.eb.v404
- ^ Estudiantes y posdoctorantes, Technion, archivado desde el original el 25 de noviembre de 2021 , consultado el 30 de septiembre de 2021.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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].
- ^ 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.
- ^ 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 .
- ^ 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.
- ^ 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 .
- ^ 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.
- ^ 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.
- ^ 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 .
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Lin Chen; Daniel Marx (2018). "Cubrir un árbol con subárboles enraizados: algoritmos de aproximación y parametrizados" (PDF) . Refresco : 2801–2820.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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 .
- ^ Shmuel Onn - Premio INFORMS Computing Society 2010, INFORMS