71 citations · 106 across the 18 of their papers we have counts for
18 papers
Cornell University Uses Integer Programming to Optimize Final Exam Scheduling
Tinghan Ye, Adam S. Jovine, Willem van Osselaer +2
This paper presents an integer programming-based optimization framework designed to effectively address the complex final exam scheduling challenges encountered at Cornell Universi…
Bounding the Price-of-Fair-Sharing using Knapsack-Cover Constraints to guide Near-Optimal Cost-Recovery Algorithms
Sander Aarts, Jacob Dentes, Manxi Wu +1
We consider the problem of fairly allocating the cost of providing a service among a set of users, where the service cost is formulated by an NP-hard {\it covering integer program…
An Interpretable Determinantal Choice Model for Subset Selection
Sander Aarts, David B. Shmoys, Alex Coy
Understanding how subsets of items are chosen from offered sets is critical to assortment planning, wireless network planning, and many other applications. There are two seemingly…
Hitting Sets when the Shallow Cell Complexity is Small
Sander Aarts, David B. Shmoys
The hitting set problem is a well-known NP-hard optimization problem in which, given a set of elements and a collection of subsets, the goal is to find the smallest selection of el…
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…
A min-max theorem for the minimum fleet-size problem
Tinghan Ye, David Shmoys
A retrospective fleet-sizing problem can be solved via bipartite matching, where a maximum cardinality matching corresponds to the minimum number of vehicles needed to cover all tr…
GILP: An Interactive Tool for Visualizing the Simplex Algorithm
Henry W. Robbins, Samuel C. Gutekunst, David B. Shmoys +1
The Simplex algorithm for solving linear programs-one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century-is an important topic in many a…
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…
Combatting Gerrymandering with Ranked Choice Voting: An Experimental Analysis of Multi-member Districts in the United States
Nikhil Garg, Wes Gurnee, David Rothschild +1
Every representative democracy must specify a mechanism under which voters choose their representatives. The most common mechanism in the United States -- Winner takes all single-m…
Fairmandering: A column generation heuristic for fairness-optimized political districting
Wes Gurnee, David B. Shmoys
The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. Existing computational solutions…
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…
On the Power of Static Assignment Policies for Robust Facility Location Problems
Omar El Housni, Vineet Goyal, David Shmoys
We consider a two-stage robust facility location problem on a metric under an uncertain demand. The decision-maker needs to decide on the (integral) units of supply for each facili…
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…
Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems
Daniel Freund, Shane G. Henderson, David B. Shmoys
The growing popularity of bike-sharing systems around the world has motivated recent attention to models and algorithms for their effective operation. Most of this literature focus…
Maximizing the Spread of Cascades Using Network Design
Daniel Sheldon, Bistra Dilkina, Adam N. Elmachtoub +8
We introduce a new optimization framework to maximize the expected spread of cascades in networks. Our model allows a rich set of actions that directly manipulate cascade dynamics…
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.