Dawid Szmojs

David Shmoys
David Shmoys
Urodzić się	1959 (wiek 63–64)
Alma Mater	Princeton , Uniwersytet Kalifornijski w Berkeley
Nagrody	Nagroda Fredericka W. Lanchestera (2013) Nagroda Daniela H. Wagnera (2018) Nagroda Khachiyana (2022)
Kariera naukowa
Pola	Informatyka , teoria złożoności obliczeniowej
Instytucje	Cornell
Praca dyplomowa	Algorytmy aproksymacji dla problemów w sekwencjonowaniu, planowaniu i projektowaniu sieci komunikacyjnych (1984)
Doradca doktorski	Eugeniusza Lawlera
Strona internetowa	ludzie .orie .cornell .edu /shmoys /

David Bernard Shmoys (ur. 1959) jest profesorem w Szkole Badań Operacyjnych i Inżynierii Informatycznej oraz na Wydziale Informatyki Uniwersytetu Cornell . Uzyskał stopień doktora. z Uniwersytetu Kalifornijskiego w Berkeley w 1984. Jego głównym celem było projektowanie i analiza algorytmów dla problemów optymalizacji dyskretnej.

W szczególności jego praca podkreśliła rolę programowania liniowego w projektowaniu algorytmów aproksymacyjnych dla problemów NP-trudnych . Znany jest ze swoich pionierskich badań nad zapewnieniem gwarancji wydajności pierwszego stałego czynnika dla kilku problemów szeregowania i grupowania, w tym problemów k-centrum i k-median oraz uogólnionego problemu przypisania. Schematy aproksymacji czasu wielomianowego , które opracował dla problemów szeregowania , znalazły zastosowanie w wielu późniejszych pracach. Jego obecne badania obejmują optymalizację stochastyczną dla modeli opartych na danych w szerokim przekroju obszarów, w tym modelowanie epidemiologiczne COVID, okręgi kongresowe, transport i projektowanie sieci IoT. Shmoys jest żonaty z Évą Tardos , która jest profesorem informatyki Jacoba Goulda Schurmana na Uniwersytecie Cornell.

Kluczowe składki

Dwa z jego kluczowych wkładów to

1. Algorytm aproksymacji współczynników stałych dla uogólnionego problemu przypisania i szeregowania niepowiązanych maszyn równoległych.
2. Algorytm aproksymacji współczynników stałych dla problemu k-median i lokalizacji obiektu .

Wkłady te zostały krótko opisane poniżej:

Uogólniony problem przypisania i niezwiązane równoległe planowanie maszyn

Artykuł jest wspólną pracą Davida Shmoysa i Evy Tardos.

Uogólniony problem przypisania można postrzegać jako następujący problem planowania niepowiązanej maszyny równoległej z kosztami. $niezależnych$ z zadań (oznaczonych $)$$musi$ być przetwarzane przez dokładnie jedną z $równoległych$ (oznaczonych . Brak powiązania oznacza, że ​​to samo zadanie może zająć różną ilość czasu przetwarzania na różnych komputerach. Praca zajmuje jednostki czasu $displaystyle p_ {i,$$}}$$j$ podczas przetwarzania przez maszynę kosztem ${\ Displaystyle c_ {i, j}, i = 1,2, ..., m; j = 1,2, ..., n; n \ geq m}$ . Biorąc ${\ Displaystyle T_ {i}, i = 1,2,.., m} , chcemy zdecydować, czy$$uwagę$ i harmonogram z całkowitym kosztem najwyżej taki, że dla każdej maszyny $displaystyle i}$${ \ displaystyle$$}$ jego obciążenie, całkowity czas przetwarzania wymagany dla przypisanych mu zadań wynosi co najwyżej ${\ Displaystyle T_ {i}, i = 1,2, ..., m$ . Skalując czasy przetwarzania, możemy założyć, bez utraty ogólności, że granice obciążenia maszyny spełniają ${\ Displaystyle T_ {1} = T_ {2} = .. = T_ {m} = T}$ . `` Innymi $"$ , uogólniony problem przypisania polega na znalezieniu harmonogramu minimalnych kosztów podlegających ograniczeniu, które powoduje, że maksymalne obciążenie maszyny wynosi co najwyżej .

praca Shmoysa z Lenstra i Tardosem daje algorytm przybliżenia 2 dla przypadku kosztów jednostkowych. Algorytm opiera się na sprytnym zaprojektowaniu programu liniowego przy użyciu przycinania parametrycznego, a następnie deterministycznego zaokrąglenia skrajnego rozwiązania programu liniowego. Algorytm uogólnionego problemu przypisania jest oparty na podobnym LP poprzez przycinanie parametryczne, a następnie przy użyciu nowej techniki zaokrąglania na starannie zaprojektowanym grafie dwudzielnym. Podajemy teraz formułę LP i krótko opisujemy technikę zaokrąglania.

Odgadujemy optymalną wartość makepan i piszemy następujący LP. ${\ displaystyle T} .$ Ta technika jest znana jako przycinanie parametryczne.

${\ Displaystyle LP (T):: \ suma _ {i = 1} ^ {m} \ suma _$ ;

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

$\ Displaystyle \ suma _ {i = 1} ^ {m} p_ {ij} x_ {ij} \ równoważnik T \ qquad i = 1,\ldkropki ,m}$ ;

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

${\ Displaystyle x_ {ij} = 0 \ qquad {\ tekst {jeśli}} \ qquad p_ {ij} \geq T,\qquad i=1,\ldots,m,\quad j=1,\ldots,n}$ ;

Otrzymane rozwiązanie LP jest następnie zaokrąglane do rozwiązania całkowego w następujący sposób. $_$ wykres _ Jedna strona dwudzielnego wykresu zawiera węzły zadań, ${\ Displaystyle W = \ {w_ {j} | j \ w J \}}$ , a druga strona zawiera kilka kopii każdego węzła maszyny, $| i = 1,2, ..., m; s = 1,2, ..., k_ {i} \}}$ gdzie ${\ Displaystyle k_ {i} = \ lceil \ suma _ {j} x_ {ij} \ rceil}$ . Aby skonstruować krawędzie węzłów maszynowych odpowiadających powiedzmy maszynie $pierwsze$ zadania są ułożone w malejącej kolejności czasu przetwarzania ${\ displaystyle p_ {ij}}$ . Dla uproszczenia załóżmy, ${\ Displaystyle p_ {i1} \ geq p_ {i2} \ geq \ ldots \ geq p_ {in}}$ . Teraz znajdź minimalny indeks taki, że ${j_ {1}} x_ {ij} \ geq 1 }$$}$ . mi ${\ displaystyle E}$ wszystkie krawędzie ${\ Displaystyle (w_ {j}, v_ {i1}, j$$ustaw$ wagi na ${\ Displaystyle x'_ {v_ {i1}j}=x_{ij}}$ . ${\ Displaystyle x'_ {v_ {i1} j_ {1}} = 1 - \ suma _ {i = 1} ^ {j_ {1} -1} x'_ {v_ {i1}j}}$ krawędź $′$ na . Zapewnia to $,$ że całkowita waga krawędzi padających na wierzchołek $displaystyle x'_ {v_ {i1} j_ {1}}<x_ {ij_ {1}}}$ co najwyżej 1. Jeśli , a następnie utwórz krawędź ${\ Displaystyle (w_ {j_ {1}}, v_ {i2})}$ z waga ${\ Displaystyle x'_ {v_ {i2} j_ {1}} = x_ {ij} -x'_ {v_ {i1} j_{1}}}$ . Kontynuuj przypisywanie krawędzi do ${\ displaystyle v_ {i2}}$ w podobny sposób.

$sposób$ grafie dwudzielnym każdy węzeł zadania w ma całkowitą wagę krawędzi 1 zdarzenia, a każdy węzeł maszyny w $.$ krawędzie o łącznej wadze co najwyżej 1 zdarzenia . Zatem wektor $jest$ przykładem dopasowania ułamkowego na dlatego można go zaokrąglić, aby uzyskać całkowite dopasowanie tego $kosztu$

Rozważając teraz kolejność czasów przetwarzania zadań na węzłach maszyn podczas budowy i używając argumentu łatwego ładowania, można udowodnić następujące twierdzenie: sol $\ displaystyle G}$

$wykonalne$ : Jeśli ma rozwiązanie, to harmonogram można skonstruować z makespan $i, j } p_ {i, j}}$ i koszt do $\ displaystyle C}$ .

Ponieważ ${\ Displaystyle max_ {i, j} p_ {i, j} \ równoważnik T}$ , uzyskuje się przybliżenie 2.

K-mediany i problem lokalizacji obiektu

Artykuł jest wspólnym dziełem Mosesa Charikara , Sudipto Guha, Évy Tardos i Davida Shmoysa. Uzyskują $przybliżenie$ k median $_$ pierwszy _

Shmoys intensywnie pracował również nad problemem lokalizacji obiektu . Jego ostatnie wyniki obejmują uzyskanie algorytmu aproksymacji problemu lokalizacji obiektu o pojemności ${\ displaystyle 3} .$ Wspólna praca z Fabianem Chudakiem zaowocowała ulepszeniem znanego wcześniej $tego$ samego problemu. Ich algorytm opiera się na wariancie zaokrąglania losowego zwanego zaokrąglaniem losowym z kopią zapasową, ponieważ rozwiązanie zapasowe jest włączone w celu skorygowania faktu, że zwykłe zaokrąglanie losowe rzadko generuje wykonalne rozwiązanie powiązanego problemu z pokryciem zestawu .

$,$ , ponownie we wspólnej pracy z udoskonalenie znanych wcześniej gwarancji zbliżenia. Udoskonalony algorytm działa na zasadzie zaokrąglenia optymalnego ułamkowego rozwiązania relaksacji programowania liniowego i wykorzystania właściwości optymalnych rozwiązań programu liniowego oraz uogólnienia techniki dekompozycji.

Nagrody i wyróżnienia

David Shmoys jest członkiem ACM Fellow , SIAM Fellow oraz Institute for Operations Research and the Management Sciences (INFORMS) (2013). Trzykrotnie otrzymał nagrodę Sonny Yau Excellence in Teaching Award od Cornell's College of Engineering i został uhonorowany nagrodą NSF Presidential Young Investigator Award, Frederick W. Lanchester Prize (2013), Daniel H. Wagner Prize for Excellence in the Practice Advanced Analytics and Operations Research (2018) oraz Nagrodę Khachiyana INFORMS Optimization Society (2022), która jest przyznawana corocznie za całokształt twórczości w dziedzinie optymalizacji.

Linki zewnętrzne

• Strona domowa Davida Shmoysa
• Strona domowa Évy Tardos