Дэвид Шмойс

Дэвид Шмойс
Дэвид Шмойс
Рожденный	1959 (64–65 лет)
Альма-матер	Принстон , Калифорнийский университет, Беркли
Награды	Премия Фредерика В. Ланчестера (2013 г.) Премия Дэниела Х. Вагнера (2018) Премия Хачияна (2022)
Научная карьера
Поля	Информатика , Теория сложности вычислений
Учреждения	Корнелл
Диссертация	Алгоритмы аппроксимации для проблем секвенирования, планирования и проектирования сетей связи   (1984)
Докторантура	Юджин Лоулер
Докторанты	Клиффорд Стейн
Веб-сайт	люди .ори .Корнелл .edu /shmoys /

Дэвид Бернард Шмойс (род. 1959) — профессор Школы исследования операций и информационной инженерии и кафедры компьютерных наук Корнелльского университета . Он получил докторскую степень. из Калифорнийского университета в Беркли в 1984 году. Его основное внимание уделялось разработке и анализу алгоритмов для решения задач дискретной оптимизации.

В частности, его работа выдвинула на первый план роль линейного программирования в разработке алгоритмов аппроксимации для NP-трудных задач. Он известен своими новаторскими исследованиями по обеспечению первой гарантии производительности постоянного фактора для нескольких задач планирования и кластеризации, включая проблемы k-центра и k-медианы, а также задачу обобщенного назначения. Схемы полиномиальной аппроксимации , разработанные им для задач планирования , нашли применение во многих последующих работах. Его текущие исследования включают стохастическую оптимизацию моделей, основанных на данных, в широком спектре областей, включая эпидемиологическое моделирование COVID, формирование избирательных округов в Конгрессе, транспорт и проектирование сетей Интернета вещей. Шмойс женат на Иве Тардос , профессоре компьютерных наук Джейкоба Гулда Шурмана в Корнелльском университете.

Ключевые вклады

Двумя его ключевыми вкладами являются

1. Алгоритм аппроксимации постоянного фактора для обобщенной задачи назначения и планирования несвязанных параллельных машин .
2. Алгоритм аппроксимации постоянным фактором для k-медиан и задачи размещения объектов .

Эти вклады кратко описаны ниже:

Обобщенная задача назначения и несвязанное планирование параллельных машин

Бумага — совместная работа Дэвида Шмойса и Евы Тардос.

Обобщенную задачу назначения можно рассматривать как следующую задачу планирования несвязанной параллельной машины со стоимостью.Каждый из $n$ самостоятельные рабочие места (обозначаются $J$) должны обрабатываться ровно одним из $m$ несвязанные параллельные машины (обозначенные $M$). Несвязанное означает, что одна и та же работа может занять разное время обработки на разных машинах. Работа $j$ берет $p_{i,j}$ единицы времени при обработке машиной $i$ и требует затрат $c_{i,j},i=1,2,..,m;j=1,2,..,n;n\geq m$. Данный $C$ и $T_{i},i=1,2,..,m$, мы хотим решить, существует ли график с общей стоимостью не более $C$ так, что для каждой машины $i$ его загруженность, общее время обработки, необходимое для порученных ему заданий, не превышает $T_{i},i=1,2,..,m$. Масштабируя время обработки, мы можем без ограничения общности предположить, что границы загрузки машины удовлетворяют $T_{1}=T_{2}=..=T_{m}=T$. «Другими словами, обобщенная задача назначения состоит в том, чтобы найти график минимальных затрат при условии, что продолжительность цикла и максимальная загрузка машины не превышают $T$ ".

Здесь цитируются работы Шмойса с Ленстрой и Тардосом дает алгоритм 2-аппроксимации для случая удельной стоимости. Алгоритм основан на продуманной конструкции линейной программы с использованием параметрического сокращения и последующего детерминированного округления решения крайней точки линейной программы. АлгоритмОбобщенная задача о назначениях основана на аналогичной ЛП посредством параметрического сокращения и последующего использования новой техники округления на тщательно разработанном двудольном графе. Сформулируем теперь формулировку ЛП и кратко опишем технику округления.

Угадываем оптимальное значение продолжительности рабочего времени $T$ и напишите следующий LP. Этот метод известен как параметрическая обрезка.

$LP(T)::\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}\leq C$;

$\sum _{i=1}^{m}x_{ij}=1\qquad j=1,\ldots ,n$;

$\sum _{i=1}^{m}p_{ij}x_{ij}\leq T\qquad i=1,\ldots ,m$;

$x_{ij}\geq 0\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n$;

$x_{ij}=0\qquad {\text{if}}\qquad p_{ij}\geq T,\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n$;

Полученное решение ЛП затем округляется до интегрального решения следующим образом. Взвешенный двудольный граф $G=(W\cup V,E)$ построен. Одна сторона двудольного графа содержит узлы заданий, $W=\{w_{j}|j\in J\}$, а другая сторона содержит несколько копий каждого машинного узла, $V=\{v_{i,s}|i=1,2,..,m;s=1,2,..,k_{i}\}$, где $k_{i}=\lceil \sum _{j}x_{ij}\rceil$. Чтобы построить ребра для узлов машины, соответствующих, скажем, машине. $i$, первые задания расположены в порядке убывания времени обработки $p_{ij}$. Для простоты предположим, что $p_{i1}\geq p_{i2}\geq \ldots \geq p_{in}$. Теперь найдем минимальный индекс $j_{1}$, такой, что $\sum _{j=1}^{j_{1}}x_{ij}\geq 1$. Включить в $E$ все края $(w_{j},v_{i1},j=1,2,..,j_{1}-1)$ с ненулевым $x_{ij}$ и установите их веса на $x'_{v_{i1}j}=x_{ij}$. Создайте преимущество $(w_{j_{1}},v_{i1})$ и установите его вес $x'_{v_{i1}j_{1}}=1-\sum _{i=1}^{j_{1}-1}x'_{v_{i1}j}$. Это гарантирует, что общий вес ребер, инцидентных вершине $v_{i1}$ не более 1. Если $x'_{v_{i1}j_{1}}<x_{ij_{1}}$, затем создайте ребро $(w_{j_{1}},v_{i2})$ с весом $x'_{v_{i2}j_{1}}=x_{ij}-x'_{v_{i1}j_{1}}$. Продолжайте назначать ребра $v_{i2}$ аналогичным образом.

В созданном таким образом двудольном графе каждый узел задания в $W$ имеет общий вес ребра, равный 1 инциденту, и каждый машинный узел в $V$ имеет ребра общей массой не более 1 инцидента на нем. Таким образом, вектор $x'$ является примером дробного сопоставления на $G$ и, таким образом, его можно округлить, чтобы получить интегральное сопоставление той же стоимости.

Теперь рассмотрим упорядочивание времени обработки работ на узлах машин при строительстве $G$ и, используя простой аргумент взимания платы, можно доказать следующую теорему:

Теорема: Если $LP(T)$ имеет допустимое решение, то расписание можно построить с помощью makepan $T+max_{i,j}p_{i,j}$ и стоимость $C$.

С $max_{i,j}p_{i,j}\leq T$, получается 2-е приближение.

K-медианы и проблема размещения объектов

Бумага — совместная работа Моисея Чарикара , Судипто Гухи , Евы Тардос и Давида Шмойса. Они получают $6{\frac {2}{3}}$ аппроксимация задачи о метрических k-медианах . Это была первая статья, сломавшая ранее известную $O(\log {k}\ \log {\log {k}})$ приближение.

Шмойс также много работал над проблемой размещения объектов . Его недавние результаты включают получение $3$ Алгоритм аппроксимации задачи размещения мощного объекта. Совместная работа с Фабианом Чудаком . привело к улучшению ранее известных $5.69$ приближение для той же задачи. Их алгоритм основан на варианте рандомизированного округления, называемом рандомизированным округлением с резервной копией, поскольку резервное решение включено для исправления того факта, что обычное рандомизированное округление редко создает осуществимое решение соответствующей проблемы покрытия множества .

Для недееспособной версии проблемы размещения объекта, опять же в совместной работе с Чудаком. он получил $(1+2/e)\approx 1.736$-алгоритм аппроксимации, который был значительным улучшением ранее известных гарантий аппроксимации.Усовершенствованный алгоритм работает путем округления оптимального дробного решения релаксации линейного программирования и использования свойств оптимальных решений линейной программы и обобщения метода декомпозиции.

Награды и почести

Дэвид Шмойс — научный сотрудник ACM , научный сотрудник SIAM и научный сотрудник Института исследований операций и наук об управлении (INFORMS) (2013). Он трижды получал Премию Сонни Яу за выдающиеся достижения в области преподавания от Инженерного колледжа Корнелла, а также был награжден Президентской премией молодого исследователя NSF, Премией Фредерика В. Ланчестера (2013 г.), Премией Дэниела Х. Вагнера за выдающиеся практические достижения. Передовой аналитики и исследований операций (2018 г.) и Премия Хачияна Общества оптимизации ИНФОРМС (2022 г.), которая вручается ежегодно за прижизненные достижения в области оптимизации.

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

• Домашняя страница Давида Шмойса
• Домашняя страница Евы Тардос