71 citations · 106 across the 18 of their papers we have counts for
7 papers · 1 filter
Scheduling with Predictions
Woo-Hyung Cho, Shane Henderson, David Shmoys
There is significant interest in deploying machine learning algorithms for diagnostic radiology, as modern learning techniques have made it possible to detect abnormalities in medi…
Scheduling Appointments Online:\\ The Power of Deferred Decision-Making
Devin Smedira, David B. Shmoys
The recently introduced online Minimum Peak Appointment Scheduling (MPAS) problem is a variant of the online bin-packing problem that allows for deferred decision making. Specifica…
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
Hyung-Chan An, Robert Kleinberg, David B. Shmoys
We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is…
Elements of Scheduling
Jan Karel Lenstra, David B. Shmoys
In the winter of 1976, Alexander Rinnooy Kan and Jan Karel Lenstra defended their PhD theses at the University of Amsterdam. Gene Lawler was on their committees. It was a natural i…
A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
Maurice Cheung, Julián Mestre, David B. Shmoys +1
We consider the following single-machine scheduling problem, which is often denoted : we are given jobs to be scheduled on a single machine, where each job h…
Improving Christofides' Algorithm for the s-t Path TSP
Hyung-Chan An, Robert Kleinberg, David B. Shmoys
We present a deterministic (1+sqrt(5))/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecifie…
LP-Based Approximation Algorithms for Traveling Salesman Path Problems
Hyung-Chan An, David B. Shmoys
This paper has been merged into 1110.4604.