Давид Шмойс

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

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

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

Ключевые вклады [ править ]

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

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}$

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

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

${\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}}$

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

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

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

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

K-медианы и проблема расположения оборудования [ править ]

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

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

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

Награды и награды [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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