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
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
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, vol. 40 (2012), pp. 98-100
VCG with Communities on Random Ad Hoc Networks
Streaming k-means on Well-Clusterable Data
Vladimir Braverman
Rafail Ostrovsky
Alan Roytman
Michael Shindler
SODA (2011), pp. 26-40
Algorithms for Constructing Overlay Networks For Live Streaming
Konstantin Andreev
Bruce M. Maggs
Jevan Saks
Ramesh K. Sitaraman
CoRR, vol. abs/1109.4114 (2011)
Scheduling under Precedence, Communication, and Energy Constraints
Fast and Accurate k-means For Large Datasets
Bandwidth and Low Dimensional Embedding
Energy-efficient mobile data transport via online multi-network packet scheduling
Simultaneous source location
Konstantin Andreev
Charles Garrod
Bruce M. Maggs
ACM Transactions on Algorithms, vol. 6 (2009)
Minimizing Average Shortest Path Distances via Shortcut Edge Addition
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
A Constant Factor Approximation for the Single Sink Edge Installation Problem
On the price of mediation
Milan Bradonjic
Gunes Ercal-Ozkaya
Alan Roytman
ACM Conference on Electronic Commerce (2009), pp. 315-324
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
Proportional Fair Frequency-Domain Packet Scheduling for 3GPP LTE Uplink
Cost-Distance: Two Metric Network Design
Frugal Routing on Wireless Ad-Hoc Networks
Randomized k-server on hierarchical binary trees
Pricing of partially compatible products
David Kempe
Nainesh Solanki
Ramnath K. Chellappa
ACM Conference on Electronic Commerce (2007), pp. 218-226
Embedding Bounded Bandwidth Graphs into l1
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
Randomized online algorithms for minimum metric bipartite matching
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
Approximate majorization and fair online load balancing
Ashish Goel
Serge A. Plotkin
ACM Transactions on Algorithms, vol. 1 (2005), pp. 338-349
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
Online algorithms for network design
SPAA (2004), pp. 275-280
Simultaneous Source Location
A k-Median Algorithm with Running Time Independent of Data Size
Approximation algorithms for deadline-TSP and vehicle routing with time-windows
On the Complexity of Optimal K-Anonymity
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
Online oblivious routing
Designing overlay multicast networks for streaming
A constant factor approximation algorithm for the fault-tolerant facility location problem
Reducing truth-telling online mechanisms to online optimization
Distributed admission control, scheduling, and routing with stale information
Using approximate majorization to characterize protocol fairness
Improved algorithms for fault tolerant facility location
Approximate majorization and fair online load balancing
Profit-earning facility location
STOC (2001), pp. 30-36
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
Online Facility Location
FOCS (2001), pp. 426-431
Web caching using access statistics
A constant factor approximation for the single sink edge installation problems
Designing Networks Incrementally
Combining Fairness with Throughput: Online Routing with Multiple Objectives
Combining fairness with throughput: online routing with multiple objectives
Hierarchical Placement and Network Design Problems
Cost-Distance: Two Metric Network Design