David Applegate
David Applegate is a Research Scientist at Google NYC, in the Large Scale Optimization group within the Algorithms and Optimization team. He came to Google in 2016, after 16 years as a Lead Member of Technical Staff in the AT&T Shannon Research Laboratory. Prior to that he spent 4 years as an Associate Professor at Rice University and 4 years as a Member of Technical Staff in AT&T Bell Labs. He has a Ph.D. in Computer Science from Carnegie Mellon (1991) and a B.S. in Computer Science and Math from the University of Dayton (1984).
David's primary research interests include large-scale mathematical optimization and applied algorithms and data structures. His secondary interests include networking, combinatorial puzzles, and integer sequences. He was named an AT&T Fellow (2013), and has received the Frederick W. Lanchester prize (INFORMS, 2007, for The Traveling Salesman: A Computational Study), the William R. Bennet prize (IEEE Communications Society, 2007, for “Making Routing Robust to Changing Traffic Demands: Algorithms and Evaluation”), the Beale-Orchard-Hays prize (Mathematical Optimization Society, 2000, for "On the Solution of Traveling Salesman Problems”), and the George Pólya award (MAA, 2013, for “Carryless Arithmetic Mod 10”). He also had a winning entry in the 8th International Obfuscated C Code Contest (1991).
David also enjoys rock climbing and supporting the New Jersey Devils and New York Red Bulls.
David's primary research interests include large-scale mathematical optimization and applied algorithms and data structures. His secondary interests include networking, combinatorial puzzles, and integer sequences. He was named an AT&T Fellow (2013), and has received the Frederick W. Lanchester prize (INFORMS, 2007, for The Traveling Salesman: A Computational Study), the William R. Bennet prize (IEEE Communications Society, 2007, for “Making Routing Robust to Changing Traffic Demands: Algorithms and Evaluation”), the Beale-Orchard-Hays prize (Mathematical Optimization Society, 2000, for "On the Solution of Traveling Salesman Problems”), and the George Pólya award (MAA, 2013, for “Carryless Arithmetic Mod 10”). He also had a winning entry in the 8th International Obfuscated C Code Contest (1991).
David also enjoys rock climbing and supporting the New Jersey Devils and New York Red Bulls.
Research Areas
Authored Publications
Sort By
Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
Mateo Díaz
Oliver Hinder
Haihao Lu
Miles Lubin
Brendan O'Donoghue
Warren Schudy
NeurIPS 2021
Preview abstract
We present PDLP, a practical first-order method for linear programming (LP) that can solve to the high levels of accuracy that are expected in traditional LP applications. In addition, it can scale to very large problems because its core operation is matrix-vector multiplications. PDLP is derived by applying the primal-dual hybrid gradient (PDHG) method, popularized by Chambolle and Pock (2011), to a saddle-point formulation of LP. PDLP enhances PDHG for LP by combining several new techniques with older tricks from the literature; the enhancements include diagonal preconditioning, presolving, adaptive step sizes, and adaptive restarting. PDLP improves the state of the art for first-order methods applied to LP. We compare PDLP with SCS, an ADMM-based solver, on a set of 383 LP instances derived from MIPLIB 2017. With a target of 10^(-8) relative accuracy and 1 hour time limit, PDLP achieves a 6.3x reduction in the geometric mean of solve times and a 4.6x reduction in the number of instances unsolved (from 227 to 49). Furthermore, we highlight standard benchmark instances and a large-scale application (PageRank) where our open-source prototype of PDLP, written in Julia, outperforms a commercial LP solver.
View details
Wireless coverage prediction via parametric shortest paths
David S. Johnson
Evdokia Nikolova
Mikkel Thorup
Proceedings of the Nineteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'18), ACM (2018), pp. 221-230
Preview abstract
When deciding where to place access points in a wireless network, it is useful to model the signal propagation loss between a proposed antenna location and the areas it may cover. The indoor dominant path (IDP) model, introduced by Wölfle et al., is shown in the literature to have good validation and generalization error, is faster to compute than competing methods, and is used in commercial software such as WinProp, iBwave Design, and CellTrace. Previously, the algorithms known for computing it involved a worst-case exponential-time tree search, with pruning heuristics to speed it up.
We prove that the IDP model can be reduced to a parametric shortest path computation on a graph derived from the walls in the floorplan. It therefore admits a quasipolynomial-time (i.e., nO(logn)) algorithm. We also give a practical approximation algorithm based on running a small constant number of shortest path computations. Its provable worst-case additive error (in dB) can be made arbitrarily small via appropriate choices of parameters, and is well below 1dB for reasonable choices. We evaluate our approximation algorithm empirically against the exact IDP model, and show that it consistently beats its theoretical worst-case bounds, solving the model exactly (i.e., no error) in the vast majority of cases.
View details
Analysis of the gift exchange problem
Moa Apagodu
Neil J.A. Sloane
Doron Zeilberger
The Electronic Journal of Combinatorics, 24 (2017), P3.9
Preview abstract
In the gift exchange game there are n players and n wrapped gifts. When a player’s number is called, that person can either choose one of the remaining wrapped gifts, or can “steal” a gift from someone who has already unwrapped it, subject to the restriction that no gift can be stolen more than a total of σ times. The problem is to determine the number of ways that the game can be played out, for given values of σ and n. Formulas and asymptotic expansions are given for these numbers. This work was inspired in part by a 2005 remark by Robert A. Proctor in the On-Line Encyclopedia of Integer Sequences.
View details
Optimal Content Placement for a Large-Scale VoD System
Vijay Gopalakrishnan
K.K. Ramakrishnan
IEEE/ACM Transactions on Networking, 24 (2016), pp. 2114-2127
Preview abstract
IPTV service providers offering Video-on-Demand currently use servers at each metropolitan office to store all the videos in their library. With the rapid increase in library sizes, it will soon become infeasible to replicate the entire library at each office. We present an approach for intelligent content placement that scales to large library sizes (e.g., 100Ks of videos). We formulate the problem as a mixed integer program (MIP) that takes into account constraints such as disk space, link bandwidth, and content popularity. To overcome the challenges of scale, we employ a Lagrangian relaxation-based decomposition technique combined with integer rounding. Our technique finds a near-optimal solution (e.g., within 1-2%) with orders of magnitude speedup relative to solving even the LP relaxation via standard software. We also present simple strategies to address practical issues such as popularity estimation, content updates, short-term popularity fluctuation, and frequency of placement updates. Using traces from an operational system, we show that our approach significantly outperforms simpler placement strategies. For instance, our MIP-based solution can serve all requests using only half the link bandwidth used by LRU or LFU cache replacement policies. We also investigate the trade-off between disk space and network bandwidth.
View details
