David Shmoys

David Shmoys
Shmoys david.jpg
David Shmoys
Geboren 1959 (Alter 62–63)
Alma Mater Princeton,
Universität von Kalifornien, Berkeley
Auszeichnungen Frederick W. Lanchester Preis (2013)
Daniel H. Wagner Preis (2018)
Wissenschaftliche Karriere
Felder Informatik, Computerkomplexitätstheorie
Institutionen Cornell
These Näherungsalgorithmen für Probleme bei der Sequenzierung, Planung und Kommunikationsnetzwerkdesign (1984)
Doktorand Eugene Lawler
Webseite Personen.orie.Cornell.edu/Shmoys/

David Bernard Shmoys (geboren 1959) ist Professor in der Forschungs- und Informationstechnik der School of Operations und die Abteilung für Computerwissenschaften bei Cornell Universität. Er erhielt seine Ph.D. von dem Universität von Kalifornien, Berkeley 1984. Sein Hauptaugenmerk lag auf dem Design und Analyse von Algorithmen für diskrete Optimierungsprobleme.

Insbesondere hat seine Arbeit die Rolle von hervorgehoben Lineares Programmieren im Design von Näherungsalgorithmen zum Np-harte Probleme. Er ist bekannt für seine Pionierforschung zur Bereitstellung der Erstfaktor-Leistungsgarantie für mehrere Planungs- und Clustering-Probleme, einschließlich der K-C-Center- und K-Median-Probleme und des allgemeinen Zuordnungsproblems. Polynom-Zeit-Annäherungsschemata dass er sich entwickelt hat Planung Probleme haben Anwendungen in vielen nachfolgenden Arbeiten gefunden. Seine aktuelle Forschung umfasst Stochastik Optimierung Für datengesteuerte Modelle in einem breiten Querschnitt von Bereichen, einschließlich Covid Epidemiological Modeling, Districting, Transportation und IoT-Netzwerkdesign. Shmoys ist verheiratet mit Éva Tardos, der der Jacob Gould Schurman Professor für Informatik an der Cornell University ist.

Schlüsselbeiträge

Zwei seiner wichtigsten Beiträge sind

  1. Algorithmus des Konstantenfaktors für die Verallgemeinerter Zuordnungsproblem und nicht verwandte Parallelmaschinenplanung.
  2. Algorithmus über Konstante Faktor -Approximation für K-Medians und Standortproblem der Einrichtung.

Diese Beiträge werden unten kurz beschrieben:

Verallgemeinerter Zuordnungsproblem und nicht verwandte Parallelmaschine Planung

Das Papier[1] ist eine gemeinsame Arbeit von David Shmoys und Eva Tardos.

Das verallgemeinerte Zuordnungsproblem kann als das folgende Problem der Planung einer nicht verwandten Parallelmaschine mit Kosten angesehen werden. Jeder von unabhängige Jobs (bezeichnet ) müssen von genau einem von verarbeitet werden nicht verwandte parallele Maschinen (bezeichnet ). Unabhängig impliziert, dass die gleiche Aufgabe bei verschiedenen Maschinen eine unterschiedliche Verarbeitungszeit in Anspruch nehmen kann. Arbeit nimmt Zeiteinheiten, wenn sie mit der Maschine verarbeitet werden und kostet Kosten . Gegeben und Wir möchten entscheiden, ob es höchstens einen Zeitplan mit Gesamtkosten gibt so dass für jede Maschine Die Last, die Gesamtbearbeitungszeit für die ihm zugewiesenen Jobs ist höchstens . Durch die Skalierung der Verarbeitungszeiten können wir ohne Verlust der Allgemeinheit annehmen, dass die Maschinenlastgrenzen erfüllen . "Mit anderen Worten, das allgemeine Zuordnungsproblem besteht darin, einen Zeitplan mit Mindestkosten zu finden, das der Einschränkung unterliegt, dass der Makespan die maximale Maschinenlast höchstens ist ".

Die Arbeit von Shmoys mit Lenstra und hier zitierte Tardos[2] Gibt einen 2 -Approximationsalgorithmus für den Einheitskostenfall an. Der Algorithmus basiert auf einem cleveren Design des linearen Programms unter Verwendung des parametrischen Beschneidens und der Rundung einer extremen Punktlösung des linearen Programms deterministisch. Der Algorithmus für das verallgemeinerte Zuordnungsproblem basiert auf einem ähnlichen LP durch parametrisches Beschneidung und dann eine neue Rundungstechnik in einem sorgfältig gestalteten zweigliedrigen Diagramm. Wir geben nun die LP -Formulierung an und beschreiben kurz die Rundungstechnik.

Wir vermuten den optimalen Wert von Makespan und schreiben Sie die folgende LP. Diese Technik wird als parametrisches Beschneidung bezeichnet.

;

;
;
;
;

Die erhaltene LP -Lösung wird dann wie folgt auf eine integrale Lösung abgerundet. Eine gewichtete zweigliedrige Grafik ist konstruiert. Eine Seite des zweiteiligen Diagramms enthält die Jobknoten. und die andere Seite enthält mehrere Kopien jedes Maschinenknotens,, wo . Konstruktion der Kanten zu maschinellen Knoten, die der Sage -Maschine entsprechen Die ersten Arbeitsplätze sind in der Verringerung der Verarbeitungszeit arrangiert . Zum Einfachheit halber, nehme an, . Finden Sie nun den Mindestindex , so dass. In einbeziehen alle Kanten mit ungleich Null und setzen ihre Gewichte auf . Erstellen Sie die Kante und setzen sein Gewicht auf . Dies stellt sicher, dass das Gesamtgewicht der auf dem Scheitelpunkt einfallenden Kanten vorliegt ist höchstens 1. wenn Erstellen Sie dann eine Kante mit Gewicht . Fahren Sie mit den Kanten weiter zu auf eine ähnliche Art und Weise.

In der so erstellten zweipartnerischen Grafik ist jeder Jobknoten in hat ein Gesamtkantengewicht von 1 Vorfall und jeder Maschinenknoten in hat Kanten mit Gesamtgewicht höchstens 1 Vorfall. So der Vektor ist eine Instanz einer fraktionalen Übereinstimmung auf und so kann es abgerundet werden, um eine integrale Anpassung der gleichen Kosten zu erhalten.

Betrachten Sie nun die Bestellung von Verarbeitungszeiten der Arbeitsplätze auf den Maschinenknoten während des Konstruktion von Und mit einem einfachen Ladeargument kann der folgende Satz nachgewiesen werden:

Satz: Wenn Hat eine praktikable Lösung, dann kann ein Zeitplan mit Makespan konstruiert werden und Kosten .

Seit Eine 2 -Näherung wird erhalten.

K-Medians und Standortproblem

Das Papier[3] ist eine gemeinsame Arbeit von Moses Charikar, Sudipto Guha, Éva Tardos und David Shmoys. Sie erhalten a Annäherung an das Metrik -K -Medianproblem. Dies war das erste Papier, das die bisher am bekanntesten bekannten Papier brach Annäherung.

Shmoys hat auch ausgiebig an der gearbeitet Standort der Einrichtung Problem. Seine jüngsten Ergebnisse sind das Erhalten von a Approximationsalgorithmus für das Standort des Kapazitätsanlagens. Die gemeinsame Arbeit mit Fabian Chudak,[4] hat zur Verbesserung der vorherigen Bekannten geführt Näherung für das gleiche Problem. Ihr Algorithmus basiert auf einer Variante von randomisierte Rundung Die randomisierte Rundung mit einer Sicherung bezeichnet, da eine Sicherungslösung eingebaut ist, um die Tatsache zu korrigieren Set Deckung Problem.

Für die im nicht fällige Version des Standortproblems der Einrichtung, wieder in einer gemeinsamen Arbeit mit Chudak[5] Er erhielt a -Anprüfungsalgorithmus, die eine signifikante Verbesserung der bisher bekannten Näherungsgarantien darstellte. Der verbesserte Algorithmus bewirkt, dass eine optimale fraktionelle Lösung einer linearen Programmierrelaxation und die Eigenschaften der optimalen Lösungen des linearen Programms und eine Verallgemeinerung einer Zersetzungstechnik verwendet wird.

Auszeichnungen und Auszeichnungen

David Shmoys ist ein ACM Fellow, a Siam Fellow, und ein Kerl der Institut für Operationsforschung und Managementwissenschaften (Informiert) (2013). Er hat den Sonny Yau Excellence in Teaching Award dreimal vom Cornell's College of Engineering erhalten und wurde mit einem NSF Presidential Young Investigator Award ausgezeichnet. Frederick W. Lanchester Preis (2013) und der Daniel H. Wagner -Preis für Exzellenz in der Praxis der fortschrittlichen Analytik- und Operations -Forschung.

Verweise

  1. ^ Shmoys, D. B.; TARDOS, é. (1993). "Ein Näherungsalgorithmus für das verallgemeinerte Zuordnungsproblem". Mathematische Programmierung. 62 (1–3): 461–474. doi:10.1007/bf01585178. S2CID 9027754.
  2. ^ Lenstra, J. K.; Shmoys, D. B.; TARDOS, é. (1990). "Näherungsalgorithmen zur Planung von nicht verwandten parallelen Maschinen". Mathematische Programmierung. 46 (1–3): 259–271. doi:10.1007/bf01585745. S2CID 206799898.
  3. ^ Charikar, M.; Guha, S.; Tardos, É.; Shmoys, D. B. (2002). "Ein Algorithmus mit konstantem Faktor-Näherungsalgorithmus für das k-medianische Problem". Journal of Computer and System Sciences. 65: 129–149. doi:10.1006/jcs.2002.1882.
  4. ^ Chudak, F. N. A.; Williamson, D. P. (2004). "Verbesserte Approximationsalgorithmen für Standortprobleme der Einrichtung". Mathematische Programmierung. 102 (2): 207. Citeseerx 10.1.1.53.5219. doi:10.1007/s10107-004-0524-9. S2CID 40133143.
  5. ^ Chudak, F. N. A.; Shmoys, D. B. (2003). "Verbesserte Approximationsalgorithmen für das Standort des nicht abgeschlossenen Einrichtungsortes". Siam Journal über Computing. 33: 1–25. doi:10.1137/s0097539703405754.

Externe Links