Adam Meyerson

Adam Meyerson

BS MIT 1997 (Math and CS double major), PhD Stanford 2002 (CS, advised by Dr. Serge Plotkin), ALADDIN Postdoc at CMU from 2002-2003, Assistant Professor at UCLA from 2003-2011. Joined Google Inc. 2011 (Dynamic Search Ads Team).
Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    Coupled and k-Sided Placements: Generalizing Generalized Assignment
    Madhukar Korupolu
    Rajmohan Rajaraman
    Integer Programming and Combinatorial Optimization (IPCO)(2014)
    Preview abstract In modern datacenters and cloud computing systems, jobs often require resources distributed across nodes providing a wide variety of services. Motivated by this, we study the Coupled Placement problem, in which we place jobs into computation and storage nodes with capacity constraints, so as to optimize some costs or profits associated with the placement. The coupled placement problem is a natural generalization of the widely-studied generalized assignment problem (GAP), which concerns the placement of jobs into single nodes providing one kind of service. We also study a further generalization, the k-Sided Placement problem, in which we place jobs into k-tuples of nodes, each node in a tuple offering one of k services. For both the coupled and k-sided placement problems, we consider minimization and maximization versions. In the minimization versions (MinCP and MinkSP), the goal is to achieve minimum placement cost, while incurring a minimum blowup in the capacity of the individual nodes. Our first main result is an algorithm for MinkSP that achieves optimal cost while increasing capacities by at most a factor of k + 1, also yielding the first constant-factor approximation for MinCP. In the maximization versions (MaxCP and MaxkSP), the goal is to maximize the total weight of the jobs that are placed under hard capacity constraints. MaxkSP can be expressed as a k-column sparse integer program, and can be approximated to within a factor of O(k) factor using randomized rounding of a linear program relaxation. We consider alternative combinatorial algorithms that are much more efficient in practice. Our second main result is a local search based approximation algorithm that yields a 15-approximation and O(k^3)-approximation for MaxCP and MaxkSP respectively. Finally, we consider an online version of MaxkSP and present algorithms that achieve logarithmic competitive ratio under certain necessary technical assumptions. View details
    Bandwidth and low dimensional embedding
    Yair Bartal
    Douglas E. Carroll
    Ofer Neiman
    Theor. Comput. Sci., 500(2013), pp. 44-56
    A tale of two metrics: simultaneous bounds on competitiveness and regret
    Lachlan L. H. Andrew
    Siddharth Barman
    Katrina Ligett
    Minghong Lin
    Alan Roytman
    Adam Wierman
    SIGMETRICS(2013), pp. 329-330
    Online Multidimensional Load Balancing
    Alan Roytman
    APPROX-RANDOM(2013), pp. 287-302
    A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret
    Lachlan L. H. Andrew
    Siddharth Barman
    Katrina Ligett
    Minghong Lin
    Alan Roytman
    Adam Wierman
    COLT(2013), pp. 741-763
    Online optimization with switching cost
    Minghong Lin
    Adam Wierman
    Alan Roytman
    Lachlan L. H. Andrew
    SIGMETRICS Performance Evaluation Review, 40(2012), pp. 98-100
    Streaming k-means on Well-Clusterable Data
    Vladimir Braverman
    Rafail Ostrovsky
    Alan Roytman
    Michael Shindler
    SODA(2011), pp. 26-40
    VCG with Communities on Random Ad Hoc Networks
    Gunes Ercal
    Rafit Izhak-Ratzin
    Rupak Majumdar
    IJDSN, 2011(2011)
    Bandwidth and Low Dimensional Embedding
    Yair Bartal
    Douglas E. Carroll
    Ofer Neiman
    APPROX-RANDOM(2011), pp. 50-61
    Scheduling under Precedence, Communication, and Energy Constraints
    David Felber
    CoRR, abs/1105.5177(2011)
    Fast and Accurate k-means For Large Datasets
    Michael Shindler
    Alex Wong
    NIPS(2011), pp. 2375-2383
    Algorithms for Constructing Overlay Networks For Live Streaming
    Konstantin Andreev
    Bruce M. Maggs
    Jevan Saks
    Ramesh K. Sitaraman
    CoRR, abs/1109.4114(2011)
    Energy-efficient mobile data transport via online multi-network packet scheduling
    Aaron Cote
    Green Computing Conference(2010), pp. 175-187
    Minimizing Average Shortest Path Distances via Shortcut Edge Addition
    APPROX-RANDOM(2009), pp. 272-285
    A Constant Factor Approximation for the Single Sink Edge Installation Problem
    Sudipto Guha
    Kamesh Munagala
    SIAM J. Comput., 38(2009), pp. 2426-2442
    Proportional Fair Frequency-Domain Packet Scheduling for 3GPP LTE Uplink
    Suk-Bok Lee
    Ioannis Pefkianakis
    Shugong Xu
    Songwu Lu
    INFOCOM(2009), pp. 2611-2615
    Incentive Compatible and Globally Efficient Position Based Routing for Selfish Reverse Multicast in Wireless Sensor Networks
    Stephan Eidenbenz
    Gunes Ercal-Ozkaya
    Allon G. Percus
    Sarvesh Kumar Varatharajan
    Algorithms, 2(2009), pp. 1303-1326
    On the price of mediation
    Milan Bradonjic
    Gunes Ercal-Ozkaya
    Alan Roytman
    ACM Conference on Electronic Commerce(2009), pp. 315-324
    Simultaneous source location
    Konstantin Andreev
    Charles Garrod
    Bruce M. Maggs
    ACM Transactions on Algorithms, 6(2009)
    Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
    Douglas E. Carroll
    APPROX-RANDOM(2009), pp. 29-41
    Frugal Routing on Wireless Ad-Hoc Networks
    Gunes Ercal
    Rafit Izhak-Ratzin
    Rupak Majumdar
    SAGT(2008), pp. 133-144
    Randomized k-server on hierarchical binary trees
    Aaron Cote
    Laura J. Poplawski
    STOC(2008), pp. 227-234
    Cost-Distance: Two Metric Network Design
    Kamesh Munagala
    Serge A. Plotkin
    SIAM J. Comput., 38(2008), pp. 1648-1659
    Pricing of partially compatible products
    David Kempe
    Nainesh Solanki
    Ramnath K. Chellappa
    ACM Conference on Electronic Commerce(2007), pp. 218-226
    Minimum failure explanations for path vector routing changes
    Mohit Lad
    Daniel Massey
    Akash Nanavati
    Lixia Zhang 0001
    J. Comb. Optim., 12(2006), pp. 5-16
    Simultaneous Optimization via Approximate Majorization for Concave Profits or Convex Costs
    Ashish Goel
    Algorithmica, 44(2006), pp. 301-323
    Randomized online algorithms for minimum metric bipartite matching
    Akash Nanavati
    Laura Poplawski
    SODA(2006), pp. 954-959
    Embedding Bounded Bandwidth Graphs into l<sub>1</sub>
    Douglas E. Carroll
    Ashish Goel
    ICALP (1)(2006), pp. 27-37
    The Power of Sequential Single-Item Auctions for Agent Coordination
    Sven Koenig
    Craig A. Tovey
    Michail G. Lagoudakis
    Evangelos Markakis
    David Kempe
    Pinar Keskinocak
    Anton J. Kleywegt
    Sonal Jain
    AAAI(2006), pp. 1625-1629
    Auction-Based Multi-Robot Routing
    Michail G. Lagoudakis
    Evangelos Markakis
    David Kempe
    Pinar Keskinocak
    Anton J. Kleywegt
    Sven Koenig
    Craig A. Tovey
    Sonal Jain
    Robotics: Science and Systems(2005), pp. 343-350
    Approximate majorization and fair online load balancing
    Ashish Goel
    Serge A. Plotkin
    ACM Transactions on Algorithms, 1(2005), pp. 338-349
    The Parking Permit Problem
    FOCS(2005), pp. 274-284
    On the Complexity of Optimal K-Anonymity
    Ryan Williams
    PODS(2004), pp. 223-228
    A <i>k</i>-Median Algorithm with Running Time Independent of Data Size
    Liadan O'Callaghan
    Serge A. Plotkin
    Machine Learning, 56(2004), pp. 61-87
    Approximation algorithms for deadline-TSP and vehicle routing with time-windows
    Nikhil Bansal
    Avrim Blum
    Shuchi Chawla
    STOC(2004), pp. 166-174
    Simultaneous Source Location
    Konstantin Andreev
    Charles Garrod
    Bruce M. Maggs
    APPROX-RANDOM(2004), pp. 13-26
    Online algorithms for network design
    SPAA(2004), pp. 275-280
    Local Search Heuristics for k-Median and Facility Location Problems
    Vijay Arya
    Naveen Garg
    Rohit Khandekar
    Kamesh Munagala
    Vinayaka Pandit
    SIAM J. Comput., 33(2004), pp. 544-562
    Online oblivious routing
    Nikhil Bansal
    Avrim Blum
    Shuchi Chawla
    SPAA(2003), pp. 44-49
    Designing overlay multicast networks for streaming
    Konstantin Andreev
    Bruce M. Maggs
    Ramesh K. Sitaraman
    SPAA(2003), pp. 149-158
    Reducing truth-telling online mechanisms to online optimization
    Baruch Awerbuch
    Yossi Azar
    STOC(2003), pp. 503-510
    A constant factor approximation algorithm for the fault-tolerant facility location problem
    Sudipto Guha
    Kamesh Munagala
    J. Algorithms, 48(2003), pp. 429-440
    Web caching using access statistics
    Kamesh Munagala
    Serge A. Plotkin
    SODA(2001), pp. 354-363
    Using approximate majorization to characterize protocol fairness
    Rishi Bhargava
    Ashish Goel
    SIGMETRICS/Performance(2001), pp. 330-331
    A constant factor approximation for the single sink edge installation problems
    Sudipto Guha
    Kamesh Munagala
    STOC(2001), pp. 383-388
    Local search heuristic for k-median and facility location problems
    Vijay Arya
    Naveen Garg
    Rohit Khandekar
    Kamesh Munagala
    Vinayaka Pandit
    STOC(2001), pp. 21-29
    Improved algorithms for fault tolerant facility location
    Sudipto Guha
    Kamesh Munagala
    SODA(2001), pp. 636-641
    Combining Fairness with Throughput: Online Routing with Multiple Objectives
    Ashish Goel
    Serge A. Plotkin
    J. Comput. Syst. Sci., 63(2001), pp. 62-79
    Distributed admission control, scheduling, and routing with stale information
    Ashish Goel
    Serge A. Plotkin
    SODA(2001), pp. 611-619
    Profit-earning facility location
    STOC(2001), pp. 30-36
    Designing Networks Incrementally
    Kamesh Munagala
    Serge A. Plotkin
    FOCS(2001), pp. 406-415
    Approximate majorization and fair online load balancing
    Ashish Goel
    Serge A. Plotkin
    SODA(2001), pp. 384-390
    Online Facility Location
    FOCS(2001), pp. 426-431
    Combining fairness with throughput: online routing with multiple objectives
    Ashish Goel
    Serge A. Plotkin
    STOC(2000), pp. 670-679
    Hierarchical Placement and Network Design Problems
    Sudipto Guha
    Kamesh Munagala
    FOCS(2000), pp. 603-612
    Cost-Distance: Two Metric Network Design
    Kamesh Munagala
    Serge A. Plotkin
    FOCS(2000), pp. 624-630