Jump to Content
David Applegate

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.
Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, desc
  • Year
  • Year, desc
    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
    Ger Yang
    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, vol. 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
    Seungjoon Lee
    K.K. Ramakrishnan
    IEEE/ACM Transactions on Networking, vol. 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
    Content placement via the exponential potential function method
    Vijay Gopalakrishnan
    Seungjoon Lee
    K.K. Ramakrishnan
    Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Springer, pp. 49-61
    Leveraging video viewing patterns for optimal content placement
    Kyung-Wook Hwang
    Vijay Gopalakrishnan
    Seungjoon Lee
    Vishal Misra
    K. K. Ramakrishnan
    Deborah F. Swayne
    NETWORKING 2012 - 11th International IFIP TC 6 Networking Conference Proceedings, Part II, pp. 44-58
    Combining predictors for recommending music: the False Positives' approach to KDD Cup track 2
    Suhrid Balakrishnan
    Rensheng Wang
    Carlos Eduardo Scheidegger
    Angus MacLellan
    Yifan Hu
    Shankar Krishnan
    Guangqin Ma
    S. Tom Au
    JMLR Proceedings, vol. 18 (2012), pp. 199-213
    Voting power and target-based site prioritization
    Steven J. Phillips
    Robert L. Pressey
    Desmond Torkornoo
    David Johnson
    Matthew E. Watts
    Biological Conservation, vol. 143 (2010), pp. 1989-1997