Дэвид Шмойс

американский математик

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

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

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

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

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

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

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

Статья ^[1] является совместной работой Дэвида Шмойса и Евы Тардос.

Обобщенную задачу назначения можно рассматривать как следующую задачу планирования несвязанных параллельных машин с затратами. Каждое из независимых заданий (обозначаемых ) должно обрабатываться ровно одной из несвязанных параллельных машин (обозначаемых ). Несвязанность подразумевает, что одно и то же задание может занимать разное количество времени обработки на разных машинах. Работа занимает единицы времени при обработке машиной и влечет за собой затраты . Учитывая и , мы хотим решить, существует ли расписание с общей стоимостью не более такого, что для каждой машины ее загрузка, общее время обработки, необходимое для назначенных ей заданий, не превышает . Масштабируя время обработки, мы можем предположить, без потери общности, что границы загрузки машин удовлетворяют . ``Другими словами, обобщенная задача назначения заключается в поиске расписания с минимальной стоимостью при ограничении, что makespan, что максимальная загрузка машин не превышает ". ${\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 через параметрическое отсечение и затем использование нового метода округления на тщательно спроектированном двудольном графе. Теперь мы сформулируем формулировку LP и кратко опишем метод округления.

Мы угадываем оптимальное значение makespan и записываем следующий 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}$;

Полученное решение LP затем округляется до целочисленного решения следующим образом. Строится взвешенный двудольный граф. Одна сторона двудольного графа содержит узлы заданий, , а другая сторона содержит несколько копий каждого узла машины, , где . Чтобы построить ребра к узлам машины, соответствующим, скажем, машине , первые задания располагаются в порядке убывания времени обработки . Для простоты предположим, . Теперь найдем минимальный индекс , такой, что . Включим во все ребра с ненулевым значением и установим их веса равными . Создадим ребро и установим его вес равным . Это гарантирует, что общий вес ребер, инцидентных вершине, не превышает 1. Если , то создадим ребро с весом . Продолжаем назначать ребра аналогичным образом. ${\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 _{j=1}^{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}}$ ${\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] является совместной работой Мозеса Чарикара , Судипто Гухи, Эвы Тардос и Дэвида Шмойса. Они получили приближение к метрической задаче k-медиан. Это была первая статья, которая сломала лучшее известное приближение. ${\displaystyle 6{\frac {2}{3}}}$ ${\displaystyle O(\log {k}\ \log {\log {k}})}$

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

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

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

Дэвид Шмойс — член ACM , член SIAM и член Института исследований операций и управленческих наук (INFORMS) (2013). Он трижды получал премию Sonny Yau Excellence in Teaching Award от Инженерного колледжа Корнелла, а также был награжден Президентской премией NSF для молодых исследователей, премией Frederick W. Lanchester Prize (2013), премией Daniel H. Wagner Prize за выдающиеся достижения в практике передовой аналитики и исследования операций (2018) и премией Khachiyan Общества оптимизации INFORMS (2022), которая ежегодно присуждается за достижения в области оптимизации.

Ссылки

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

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

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