# 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

Bandwidth and low dimensional embedding

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

Online Multidimensional Load Balancing

Online optimization with switching cost

Minghong Lin

Adam Wierman

Alan Roytman

Lachlan L. H. Andrew

SIGMETRICS Performance Evaluation Review, 40(2012), pp. 98-100

Algorithms for Constructing Overlay Networks For Live Streaming

Konstantin Andreev

Bruce M. Maggs

Jevan Saks

Ramesh K. Sitaraman

CoRR, abs/1109.4114(2011)

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

Fast and Accurate k-means For Large Datasets

Bandwidth and Low Dimensional Embedding

Scheduling under Precedence, Communication, and Energy Constraints

Energy-efficient mobile data transport via online multi-network packet scheduling

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

Simultaneous source location

Konstantin Andreev

Charles Garrod

Bruce M. Maggs

ACM Transactions on Algorithms, 6(2009)

Proportional Fair Frequency-Domain Packet Scheduling for 3GPP LTE Uplink

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

Minimizing Average Shortest Path Distances via Shortcut Edge Addition

Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs

Frugal Routing on Wireless Ad-Hoc Networks

Cost-Distance: Two Metric Network Design

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 l<sub>1</sub>

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

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

Randomized online algorithms for minimum metric bipartite matching

Simultaneous Optimization via Approximate Majorization for Concave Profits or Convex Costs

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

The Parking Permit Problem

FOCS(2005), pp. 274-284

A <i>k</i>-Median Algorithm with Running Time Independent of Data Size

Simultaneous Source Location

Approximation algorithms for deadline-TSP and vehicle routing with time-windows

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

On the Complexity of Optimal K-Anonymity

Reducing truth-telling online mechanisms to online optimization

Online oblivious routing

A constant factor approximation algorithm for the fault-tolerant facility location problem

Designing overlay multicast networks for streaming

Profit-earning facility location

STOC(2001), pp. 30-36

Designing Networks Incrementally

Approximate majorization and fair online load balancing

Improved algorithms for fault tolerant facility location

A constant factor approximation for the single sink edge installation problems

Online Facility Location

FOCS(2001), pp. 426-431

Using approximate majorization to characterize protocol fairness

Distributed admission control, scheduling, and routing with stale information

Web caching using access statistics

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

Combining Fairness with Throughput: Online Routing with Multiple Objectives

Cost-Distance: Two Metric Network Design

Combining fairness with throughput: online routing with multiple objectives

Hierarchical Placement and Network Design Problems