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).
Research Areas
Authored Publications
Google Publications
Other Publications
Sort By
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
Online Multidimensional Load Balancing
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
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
Bandwidth and low dimensional embedding
Yair Bartal
Douglas E. Carroll
Ofer Neiman
Theor. Comput. Sci., vol. 500 (2013), pp. 44-56
Online optimization with switching cost
Minghong Lin
Adam Wierman
Alan Roytman
Lachlan L. H. Andrew
SIGMETRICS Performance Evaluation Review, vol. 40 (2012), pp. 98-100
Fast and Accurate k-means For Large Datasets
Scheduling under Precedence, Communication, and Energy Constraints
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
Algorithms for Constructing Overlay Networks For Live Streaming
Konstantin Andreev
Bruce M. Maggs
Jevan Saks
Ramesh K. Sitaraman
CoRR, vol. abs/1109.4114 (2011)
Bandwidth and Low Dimensional Embedding
Energy-efficient mobile data transport via online multi-network packet scheduling
Proportional Fair Frequency-Domain Packet Scheduling for 3GPP LTE Uplink
Simultaneous source location
Konstantin Andreev
Charles Garrod
Bruce M. Maggs
ACM Transactions on Algorithms, vol. 6 (2009)
A Constant Factor Approximation for the Single Sink Edge Installation Problem
Minimizing Average Shortest Path Distances via Shortcut Edge Addition
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, vol. 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
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
Cost-Distance: Two Metric Network Design
Randomized k-server on hierarchical binary trees
Frugal Routing on Wireless Ad-Hoc Networks
Pricing of partially compatible products
David Kempe
Nainesh Solanki
Ramnath K. Chellappa
ACM Conference on Electronic Commerce (2007), pp. 218-226
Randomized online algorithms for minimum metric bipartite matching
Minimum failure explanations for path vector routing changes
Mohit Lad
Daniel Massey
Akash Nanavati
Lixia Zhang 0001
J. Comb. Optim., vol. 12 (2006), pp. 5-16
Simultaneous Optimization via Approximate Majorization for Concave Profits or Convex Costs
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
Embedding Bounded Bandwidth Graphs into l1
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
The Parking Permit Problem
FOCS (2005), pp. 274-284
Approximate majorization and fair online load balancing
Ashish Goel
Serge A. Plotkin
ACM Transactions on Algorithms, vol. 1 (2005), pp. 338-349
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., vol. 33 (2004), pp. 544-562
A k-Median Algorithm with Running Time Independent of Data Size
Simultaneous Source Location
Approximation algorithms for deadline-TSP and vehicle routing with time-windows
On the Complexity of Optimal K-Anonymity
Designing overlay multicast networks for streaming
A constant factor approximation algorithm for the fault-tolerant facility location problem
Online oblivious routing
Reducing truth-telling online mechanisms to online optimization
Designing Networks Incrementally
A constant factor approximation for the single sink edge installation problems
Improved algorithms for fault tolerant facility location
Using approximate majorization to characterize protocol fairness
Web caching using access statistics
Online Facility Location
FOCS (2001), pp. 426-431
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
Profit-earning facility location
STOC (2001), pp. 30-36
Combining Fairness with Throughput: Online Routing with Multiple Objectives
Approximate majorization and fair online load balancing
Distributed admission control, scheduling, and routing with stale information
Hierarchical Placement and Network Design Problems
Combining fairness with throughput: online routing with multiple objectives
Cost-Distance: Two Metric Network Design
