Давид Шмойс - David Shmoys

Давид Шмойс
Давид Шмойс
Родился	1959 (60–61 лет)
Альма-матер	Принстон, Калифорнийский университет в Беркли
Награды	Премия Фредерика В. Ланчестера (2013)
Научная карьера
Поля	Информатика, Теория вычислительной сложности
Учреждения	Корнелл
Тезис	Алгоритмы аппроксимации для задач построения последовательности, планирования и коммуникационной сети (1984)
Докторант	Юджин Лоулер
Интернет сайт	люди.orie.cornell.edu/ шмойс/

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

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

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

Два его ключевых вклада:

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

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

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

Бумага^[1] - совместная работа Давида Шмойса и Евы Тардос.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Награды и награды

Давид Шмойс Член ACM и член Институт исследований операций и управленческих наук (ИНФОРМАЦИЯ) (2013). Он трижды получал награду инженерного колледжа Сонни Яу за выдающиеся достижения в области преподавания и был награжден президентской премией NSF для молодых исследователей и награждением Премия Фредерика В. Ланчестера (2013)

использованная литература

1. Шмойс, Д.; Тардос, Э. (1993). «Алгоритм аппроксимации для обобщенной задачи о назначениях». Математическое программирование. 62 (1–3): 461–474. Дои:10.1007 / BF01585178. S2CID  9027754.
2. Lenstra, J. K .; Шмойс, Д.; Тардос, Э. (1990). «Алгоритмы аппроксимации для планирования несвязанных параллельных машин». Математическое программирование. 46 (1–3): 259–271. Дои:10.1007 / BF01585745. S2CID  206799898.
3. Charikar, M .; Guha, S .; Tardos, É .; Шмойс, Д. (2002). «Алгоритм приближения постоянного фактора для k-медианной проблемы». Журнал компьютерных и системных наук. 65: 129–149. Дои:10.1006 / jcss.2002.1882.
4. Чудак, Ф. Н. А .; Уильямсон, Д. П. (2004). «Улучшенные алгоритмы аппроксимации для задач размещения емкостных объектов». Математическое программирование. 102 (2): 207. CiteSeerX  10.1.1.53.5219. Дои:10.1007 / s10107-004-0524-9. S2CID  40133143.
5. Чудак, Ф. Н. А .; Шмойс, Д. (2003). «Улучшенные алгоритмы аппроксимации для проблемы размещения неработающих производственных объектов». SIAM Журнал по вычислениям. 33: 1–25. Дои:10.1137 / S0097539703405754.

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

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