Шмуэль Онн

Шмуэль Онн
Шмуэль Онн
Рожденный	1960 ; Израиль
Национальность	Израильский
Альма-матер	Технион ; Корнелльский университет
Супруг	Рут
Дети	Амос и Ноеминь
	Научная карьера
Поля	Исследование операций , Математика
Учреждения	Технион
Диссертация	Дискретная геометрия, групповые представления и комбинаторная оптимизация: взаимодействие (1992)
Докторантура	Луис Дж. Биллера , Бернд Штурмфельс , Лесли Э. Троттер мл.

Шмуэль Онн (ивр. שמואל און; родился в 1960 г.) — математик , профессор исследования операций и заведующий кафедрой Дрездера в Технионе — Израильском технологическом институте . ^{[ 1 ]} Он известен своим вкладом в целочисленное программирование и нелинейную комбинаторную оптимизацию . ^{[ 2 ]}

Образование

Шмуэль Онн получил начальное образование в Кадури ( он ). ^{[ 3 ]} Он получил степень бакалавра наук. (с отличием) в области электротехники в Технионе в 1980 году и после обязательной службы на военно-морском флоте получил степень магистра наук. из Техниона в 1987 году. ^{[ 3 ]} Онн получил докторскую степень. в 1992 году изучал исследования операций в Корнелльском университете со специальностями в области прикладной математики и информатики . Его диссертация «Дискретная геометрия, групповые представления и комбинаторная оптимизация: взаимодействие» была написана консультантами Луи Дж. Биллеры , Бернда Штурмфельса и Лесли Э. Троттер младший. ^{[ 4 ]}

В 1992–1993 годах он был научным сотрудником DIMACS . ^{[ 5 ]} а в 1993-1994 годах он был научным сотрудником Александра фон Гумбольдта в Университете Пассау , Германия . ^{[ 3 ]}

Карьера

В 1994 году Онн поступил на факультет обработки данных и принятия решений Техниона, где в настоящее время является профессором и заведующим кафедрой Dresner. Он также был приглашенным профессором и лектором по диплому в математических исследований Институте ETH Zürich в 2009 году. ^{[ 6 ]} и приглашенный профессор математического факультета Калифорнийского университета в Дэвисе (2001–2002 гг.). ^{[ 7 ]} Профессор Онн также долгое время посещал различные математические исследовательские институты, включая Миттаг-Леффлера в Стокгольме , MSRI в Беркли , ^{[ 8 ]} и Обервольфах в Германии. ^{[ 9 ]} Он также работал заместителем редактора отдела математики исследования операций в 2010–2016 годах. ^{[ 10 ]} и заместитель редактора отдела дискретной оптимизации в 2004–2010 гг. ^{[ 3 ]}

Онн консультировал нескольких студентов и постдокторантов, которые продолжили академическую карьеру, в том числе Антуана Деза, Шарон Авиран, Тала Равива, Нира Халмана и Мартина Кутецкого. ^{[ 11 ]}

Исследовать

Шмуэль Онн известен своим вкладом в целочисленное программирование и нелинейную комбинаторную оптимизацию . В частности, он разработал алгоритмическую теорию линейного и нелинейного целочисленного программирования в переменной размерности с использованием базисов Грейвера . ^{[ 2 ]} В этой работе была представлена теория блочного и n-кратного целочисленного программирования. ^{[ 12 ]}^{[ 13 ]} и более широкая теория целочисленного программирования с разреженной и ограниченной древовидной глубиной, которая, как показано, легко обрабатывается с фиксированными параметрами. ^{[ 14 ]}^{[ 15 ]}^{[ 16 ]} Эти теории были поддержаны другими авторами, ^{[ 17 ]}^{[ 18 ]}^{[ 19 ]}^{[ 20 ]}^{[ 21 ]}^{[ 22 ]} и имеют применение в различных областях. ^{[ 23 ]} ^{[ 24 ]}^{[ 25 ]}^{[ 26 ]}^{[ 27 ]}^{[ 28 ]}

Некоторые другие разработки Onn включают в себя структуру, которая использует направления ребер для решения выпуклые многокритериальные задачи комбинаторной оптимизации и их приложения, ^{[ 29 ]}^{[ 30 ]}^{[ 31 ]} теорема универсальности, показывающая, что каждая целочисленная программа работает над тонкими трехмерными таблицами, ^{[ 32 ]}^{[ 33 ]} определение сложности последовательностей степеней гиперграфа, ^{[ 34 ]} и введение красочного линейного программирования. ^{[ 35 ]}

Почести и награды

2010, INFORMS (ICS). Премия вычислительного общества ^{[ 36 ]}
2009 г., лектор по диплому , Институт математических исследований, ETH Zürich. ^{[ 6 ]}

Книги

Нелинейная дискретная оптимизация: алгоритмическая теория. Цюрихские лекции по высшей математике. Европейское математическое общество (EMS), Цюрих, 2010. ^{[ 2 ]}

Личная жизнь

Шмуэль женат на Руфи. У них двое детей, Амос и Наоми, они живут в Хайфе .

Внешние ссылки

Шмуэль Онн (личная страница). Архивировано 2 июля 2020 г. в Wayback Machine , Технион.
Шмуэль Онн , Технион
Серия видеолекций по нелинейной дискретной оптимизации в MSRI, Беркли

Ссылки

^ Шмуэль Онн , Технион
^ Jump up to: ^а ^б ^с Шмуэль Онн. Нелинейная дискретная оптимизация: алгоритмическая теория , Европейское математическое общество, 2010.
^ Jump up to: ^а ^б ^с ^д Сокращенное резюме , Технион, заархивировано из оригинала 25 ноября 2021 г. , получено 30 сентября 2021 г.
^ Шмуэль Онн , Проект математической генеалогии
^ Предыдущие постдокторанты DIMACS , Университет Рутгерса
^ Jump up to: ^а ^б Лекции Nachdiplom - Прошлые лекции , ETH
^ Математические коллоквиумы и семинары , Калифорнийский университет в Дэвисе
^ Личный профиль доктора Шмуэля Онна , Научно-исследовательский институт математических наук
^ Парные исследования - 2007 (PDF) , Математический научно-исследовательский институт Обервольфаха.
^ «Редакция», Математика исследования операций , 40 (4), ИНФОРМ: c2–c3, 2015, doi : 10.1287/moor.2015.eb.v404
^ Студенты и постдокторанты , Технион, архивировано из оригинала 25 ноября 2021 г. , получено 30 сентября 2021 г.
^ Раймонд Хеммеке; Шмуэль Онн; Любовь Романчук (2013). «N-кратное целочисленное программирование в кубическом времени» . Математическое программирование . 137 (1–2): 325–341. arXiv : 1101.3267 . дои : 10.1007/s10107-011-0490-y . S2CID 964450 .
^ Хесус Де Лоэра ; Раймонд Хеммеке; Шмуэль Онн; Роберт Вейсмантель (2008). «N-кратное целочисленное программирование» . Дискретная оптимизация . Памяти Джорджа Б. Данцига. 5 (2): 231–241. дои : 10.1016/j.disopt.2006.06.006 . S2CID 997926 .
^ Мартин Кутецкий; Шмуэль Онн (2021). «Программирование разреженных целых чисел — это FPT» . Бюллетень Европейской ассоциации теоретической информатики . 2 (134): 69–71.
^ Фридрих Эйзенбранд ; Кристоф Хункеншредер; Ким-Мануэль Кляйн; Мартин Кутецкий; Асаф Левин; Шмуэль Онн (2019). «Алгоритмическая теория целочисленного программирования». arXiv : 1904.01361 [ math.OC ].
^ Мартин Кутецкий; Асаф Левин; Шмуэль Онн (2018). «Параметризованный сильно полиномиальный алгоритм для целочисленных программ с блочной структурой» (PDF) . ИКАЛП . Международные труды Лейбница по информатике (LIPIcs). 107 : 85:1–85:14. arXiv : 1802.05859 . doi : 10.4230/LIPIcs.ICALP.2018.85 . ISBN 9783959770767 . S2CID 3336201 .
^ Яна Чсловечек; Фридрих Эйзенбранд; Кристоф Хункеншредер; Ким-Мануэль Кляйн; Ларс Роведдер; Роберт Вейсмантель (2021). «Блочно-структурированное целочисленное и линейное программирование в строго полиномиальном и почти линейном времени» . СОДА : 1666–1681. arXiv : 2002.07745 .
^ Корнелиус Бранд; Мартин Кутецкий; Себастьян Ордыняк (2021). «Параметризованные алгоритмы для MILP с малой глубиной дерева» . АААИ . 35 (14): 12249–12257. arXiv : 1912.03501 . дои : 10.1609/aaai.v35i14.17454 . S2CID 208909901 .
^ Тимоти Ф.Н. Чан; Джейкоб В. Купер; Мартин Кутецкий; Дэниел Кинг»; Кристина Пекаркова (2020). «Матрицы оптимальной глубины дерева и параметризованные алгоритмы, инвариантные к строкам, для целочисленного программирования» (PDF) . ICALP : 26:1–26:19. arXiv : 1907.06688 .
^ Клаус Янсен; Александра Лассота; Ларс Роведдер (2019). «Почти линейный временной алгоритм для n-кратных ILP с помощью цветового кодирования» . ИКАЛП . Международные труды Лейбница по информатике (LIPIcs). 132 : 75:1–75:13. doi : 10.4230/LIPIcs.ICALP.2019.75 . ISBN 9783959771092 . S2CID 53300379 .
^ Эдуард Эйбен; Роберт Ганьян; Душан Кноп; Ким-Мануэль Кляйн; Себастьян Ордыняк; Михал Пилипчук; Марцин Вречная (2019). «Целочисленное программирование и глубина дерева заболеваемости». Целочисленное программирование и комбинаторная оптимизация (PDF) . Конспекты лекций по информатике. Том. 11480. стр. 194–204. arXiv : 2012.00079 . дои : 10.1007/978-3-030-17953-3_15 . ISBN 978-3-030-17953-3 . S2CID 142503705 .
^ Фридрих Эйзенбранд; Кристоф Хункеншредер; Ким-Мануэль Кляйн (2018). «Более быстрые алгоритмы для целочисленных программ с блочной структурой» (PDF) . ICALP : 49:1–49:13. arXiv : 1802.06289 .
^ Душан Кноп; Мартин Кутецкий; Маттиас Мних (2020). «Голосование и подкуп в одноэкспоненциальное время» . Транзакции ACM по экономике и вычислениям . 8 (3): 12:1–12:28. arXiv : 1812.01852 . дои : 10.1145/3396855 . S2CID 218529858 .
^ Роберт Бредерек; Петр Фалишевский; Рольф Нидермайер ; Петр Сковрон; Нимрод Талмон (2020). «Смешанное целочисленное программирование с выпуклыми/вогнутыми ограничениями: управляемость с фиксированными параметрами и приложения для множественного покрытия и голосования» . Теоретическая информатика . 814 : 86–105. arXiv : 1709.02850 . дои : 10.1016/j.tcs.2020.01.017 . S2CID 3227033 .
^ Душан Кноп; Мартин Кутецкий; Маттиас Мних (2020). «Комбинаторное n-кратное целочисленное программирование и приложения» . Математическое программирование . 184 (1): 1–34. arXiv : 1705.08657 . дои : 10.1007/s10107-019-01402-2 . S2CID 213316783 .
^ Клаус Янсен; Ким-Мануэль Кляйн; Мартен Маак; Малин Рау (2019). «Расширение возможностей Configuration-IP — новые результаты PTAS для планирования с учетом времени настройки» . ITCS - Инновации в теоретической информатике . Международные труды Лейбница по информатике (LIPIcs). 124 : 44:1–44:19. doi : 10.4230/LIPIcs.ITCS.2019.44 . ISBN 9783959770958 . S2CID 24006600 .
^ Душан Кноп; Мартин Кутецкий (2018). «Планирование соответствует n-кратному целочисленному программированию» . Журнал планирования . 21 (5): 493–503. arXiv : 1603.02611 . дои : 10.1007/s10951-017-0550-0 . S2CID 9627563 .
^ Линь Чен; Даниэль Маркс (2018). «Покрытие дерева корневыми поддеревьями — параметризованные и аппроксимационные алгоритмы» (PDF) . СОДА : 2801–2820.
^ Шмуэль Онн; Уриэль Ротблюм (2004). «Выпуклая комбинаторная оптимизация» (PDF) . Дискретная и вычислительная геометрия . 32 (4): 549–566. дои : 10.1007/s00454-004-1138-y . S2CID 803661 .
^ Эрик Бэбсон; Шмуэль Онн; Рекха Томас (2003). «Зонотоп Гильберта и алгоритм полиномиального времени для универсальных базисов Гробнера» . Достижения прикладной математики . 30 (3): 529–544. arXiv : math/0207135 . дои : 10.1016/S0196-8858(02)00509-2 . S2CID 7178467 .
^ Фрэнк Хван; Шмуэль Онн; Уриэль Ротблюм (1999). «Алгоритм с полиномиальным временем для решения задач фигурного разбиения» . SIAM Journal по оптимизации . 10 : 70–81. дои : 10.1137/S1052623497344002 .
^ Хесус Де Лоэра; Шмуэль Онн (2006). «Все линейные и целочисленные программы представляют собой тонкие программы трехсторонней транспортировки» (PDF) . SIAM Journal по оптимизации . 17 (3): 806–821. дои : 10.1137/040610623 .
^ Хесус Де Лоэра; Шмуэль Онн (2004). «Сложность трехсторонних статистических таблиц» (PDF) . SIAM Journal по вычислительной технике . 33 (4): 819–836. arXiv : math/0207200 . дои : 10.1137/S0097539702403803 . S2CID 14941545 .
^ Антуан Деза; Асаф Левин; Сайед М. Мисам; Шмуэль Онн (2018). «Оптимизация последовательностей степеней» . SIAM Journal по дискретной математике . 32 (3): 2067–2079. arXiv : 1706.03951 . дои : 10.1137/17M1134482 . S2CID 52039639 .
^ Имре Барань ; Шмуэль Онн (1997). «Красочное линейное программирование и его родственники» (PDF) . Математика исследования операций . 22 (3): 550–567. дои : 10.1287/moor.22.3.550 . Архивировано из оригинала (PDF) 25 ноября 2021 г. Проверено 23 сентября 2021 г.
^ Шмуэль Онн - Премия вычислительного общества INFORMS , 2010 г., INFORMS

[1] Шмуэль Онн , Технион

[book-2] Jump up to: ^а ^б ^с Шмуэль Онн. Нелинейная дискретная оптимизация: алгоритмическая теория , Европейское математическое общество, 2010.

[cv-3] Jump up to: ^а ^б ^с ^д Сокращенное резюме , Технион, заархивировано из оригинала 25 ноября 2021 г. , получено 30 сентября 2021 г.

[4] Шмуэль Онн , Проект математической генеалогии

[5] Предыдущие постдокторанты DIMACS , Университет Рутгерса

[eth-6] Jump up to: ^а ^б Лекции Nachdiplom - Прошлые лекции , ETH

[7] Математические коллоквиумы и семинары , Калифорнийский университет в Дэвисе

[8] Личный профиль доктора Шмуэля Онна , Научно-исследовательский институт математических наук

[9] Парные исследования - 2007 (PDF) , Математический научно-исследовательский институт Обервольфаха.

[10] «Редакция», Математика исследования операций , 40 (4), ИНФОРМ: c2–c3, 2015, doi : 10.1287/moor.2015.eb.v404

[11] Студенты и постдокторанты , Технион, архивировано из оригинала 25 ноября 2021 г. , получено 30 сентября 2021 г.

[12] Раймонд Хеммеке; Шмуэль Онн; Любовь Романчук (2013). «N-кратное целочисленное программирование в кубическом времени» . Математическое программирование . 137 (1–2): 325–341. arXiv : 1101.3267 . дои : 10.1007/s10107-011-0490-y . S2CID 964450 .

[13] Хесус Де Лоэра ; Раймонд Хеммеке; Шмуэль Онн; Роберт Вейсмантель (2008). «N-кратное целочисленное программирование» . Дискретная оптимизация . Памяти Джорджа Б. Данцига. 5 (2): 231–241. дои : 10.1016/j.disopt.2006.06.006 . S2CID 997926 .

[14] Мартин Кутецкий; Шмуэль Онн (2021). «Программирование разреженных целых чисел — это FPT» . Бюллетень Европейской ассоциации теоретической информатики . 2 (134): 69–71.

[15] Фридрих Эйзенбранд ; Кристоф Хункеншредер; Ким-Мануэль Кляйн; Мартин Кутецкий; Асаф Левин; Шмуэль Онн (2019). «Алгоритмическая теория целочисленного программирования». arXiv : 1904.01361 [ math.OC ].

[16] Мартин Кутецкий; Асаф Левин; Шмуэль Онн (2018). «Параметризованный сильно полиномиальный алгоритм для целочисленных программ с блочной структурой» (PDF) . ИКАЛП . Международные труды Лейбница по информатике (LIPIcs). 107 : 85:1–85:14. arXiv : 1802.05859 . doi : 10.4230/LIPIcs.ICALP.2018.85 . ISBN 9783959770767 . S2CID 3336201 .

[17] Яна Чсловечек; Фридрих Эйзенбранд; Кристоф Хункеншредер; Ким-Мануэль Кляйн; Ларс Роведдер; Роберт Вейсмантель (2021). «Блочно-структурированное целочисленное и линейное программирование в строго полиномиальном и почти линейном времени» . СОДА : 1666–1681. arXiv : 2002.07745 .

[18] Корнелиус Бранд; Мартин Кутецкий; Себастьян Ордыняк (2021). «Параметризованные алгоритмы для MILP с малой глубиной дерева» . АААИ . 35 (14): 12249–12257. arXiv : 1912.03501 . дои : 10.1609/aaai.v35i14.17454 . S2CID 208909901 .

[19] Тимоти Ф.Н. Чан; Джейкоб В. Купер; Мартин Кутецкий; Дэниел Кинг»; Кристина Пекаркова (2020). «Матрицы оптимальной глубины дерева и параметризованные алгоритмы, инвариантные к строкам, для целочисленного программирования» (PDF) . ICALP : 26:1–26:19. arXiv : 1907.06688 .

[20] Клаус Янсен; Александра Лассота; Ларс Роведдер (2019). «Почти линейный временной алгоритм для n-кратных ILP с помощью цветового кодирования» . ИКАЛП . Международные труды Лейбница по информатике (LIPIcs). 132 : 75:1–75:13. doi : 10.4230/LIPIcs.ICALP.2019.75 . ISBN 9783959771092 . S2CID 53300379 .

[21] Эдуард Эйбен; Роберт Ганьян; Душан Кноп; Ким-Мануэль Кляйн; Себастьян Ордыняк; Михал Пилипчук; Марцин Вречная (2019). «Целочисленное программирование и глубина дерева заболеваемости». Целочисленное программирование и комбинаторная оптимизация (PDF) . Конспекты лекций по информатике. Том. 11480. стр. 194–204. arXiv : 2012.00079 . дои : 10.1007/978-3-030-17953-3_15 . ISBN 978-3-030-17953-3 . S2CID 142503705 .

[22] Фридрих Эйзенбранд; Кристоф Хункеншредер; Ким-Мануэль Кляйн (2018). «Более быстрые алгоритмы для целочисленных программ с блочной структурой» (PDF) . ICALP : 49:1–49:13. arXiv : 1802.06289 .

[23] Душан Кноп; Мартин Кутецкий; Маттиас Мних (2020). «Голосование и подкуп в одноэкспоненциальное время» . Транзакции ACM по экономике и вычислениям . 8 (3): 12:1–12:28. arXiv : 1812.01852 . дои : 10.1145/3396855 . S2CID 218529858 .

[24] Роберт Бредерек; Петр Фалишевский; Рольф Нидермайер ; Петр Сковрон; Нимрод Талмон (2020). «Смешанное целочисленное программирование с выпуклыми/вогнутыми ограничениями: управляемость с фиксированными параметрами и приложения для множественного покрытия и голосования» . Теоретическая информатика . 814 : 86–105. arXiv : 1709.02850 . дои : 10.1016/j.tcs.2020.01.017 . S2CID 3227033 .

[25] Душан Кноп; Мартин Кутецкий; Маттиас Мних (2020). «Комбинаторное n-кратное целочисленное программирование и приложения» . Математическое программирование . 184 (1): 1–34. arXiv : 1705.08657 . дои : 10.1007/s10107-019-01402-2 . S2CID 213316783 .

[26] Клаус Янсен; Ким-Мануэль Кляйн; Мартен Маак; Малин Рау (2019). «Расширение возможностей Configuration-IP — новые результаты PTAS для планирования с учетом времени настройки» . ITCS - Инновации в теоретической информатике . Международные труды Лейбница по информатике (LIPIcs). 124 : 44:1–44:19. doi : 10.4230/LIPIcs.ITCS.2019.44 . ISBN 9783959770958 . S2CID 24006600 .

[27] Душан Кноп; Мартин Кутецкий (2018). «Планирование соответствует n-кратному целочисленному программированию» . Журнал планирования . 21 (5): 493–503. arXiv : 1603.02611 . дои : 10.1007/s10951-017-0550-0 . S2CID 9627563 .

[28] Линь Чен; Даниэль Маркс (2018). «Покрытие дерева корневыми поддеревьями — параметризованные и аппроксимационные алгоритмы» (PDF) . СОДА : 2801–2820.

[29] Шмуэль Онн; Уриэль Ротблюм (2004). «Выпуклая комбинаторная оптимизация» (PDF) . Дискретная и вычислительная геометрия . 32 (4): 549–566. дои : 10.1007/s00454-004-1138-y . S2CID 803661 .

[30] Эрик Бэбсон; Шмуэль Онн; Рекха Томас (2003). «Зонотоп Гильберта и алгоритм полиномиального времени для универсальных базисов Гробнера» . Достижения прикладной математики . 30 (3): 529–544. arXiv : math/0207135 . дои : 10.1016/S0196-8858(02)00509-2 . S2CID 7178467 .

[31] Фрэнк Хван; Шмуэль Онн; Уриэль Ротблюм (1999). «Алгоритм с полиномиальным временем для решения задач фигурного разбиения» . SIAM Journal по оптимизации . 10 : 70–81. дои : 10.1137/S1052623497344002 .

[32] Хесус Де Лоэра; Шмуэль Онн (2006). «Все линейные и целочисленные программы представляют собой тонкие программы трехсторонней транспортировки» (PDF) . SIAM Journal по оптимизации . 17 (3): 806–821. дои : 10.1137/040610623 .

[33] Хесус Де Лоэра; Шмуэль Онн (2004). «Сложность трехсторонних статистических таблиц» (PDF) . SIAM Journal по вычислительной технике . 33 (4): 819–836. arXiv : math/0207200 . дои : 10.1137/S0097539702403803 . S2CID 14941545 .

[34] Антуан Деза; Асаф Левин; Сайед М. Мисам; Шмуэль Онн (2018). «Оптимизация последовательностей степеней» . SIAM Journal по дискретной математике . 32 (3): 2067–2079. arXiv : 1706.03951 . дои : 10.1137/17M1134482 . S2CID 52039639 .

[35] Имре Барань ; Шмуэль Онн (1997). «Красочное линейное программирование и его родственники» (PDF) . Математика исследования операций . 22 (3): 550–567. дои : 10.1287/moor.22.3.550 . Архивировано из оригинала (PDF) 25 ноября 2021 г. Проверено 23 сентября 2021 г.

[36] Шмуэль Онн - Премия вычислительного общества INFORMS , 2010 г., INFORMS

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

Базы данных авторитетного контроля
Международный	ЯВЛЯЮТСЯ ВИАФ WorldCat
Национальный	Франция Данные БНФ Германия Израиль Соединенные Штаты
академики	MathSciNet Проект математической генеалогии zbMATH
Другой	ИдРеф