Approximation Algorithms Publications

Avrim Blum, Shuchi Chawla, David Karger, Terran Lane, Adam Meyerson, and Maria Minkoff. Approximation Algorithms for Orienteering and Discounted-Reward TSP. SIAM Journal on Computing, 2006 (conference version in FOCS 2003).
Konstantin Andreev, Charles Garrod, Bruce Maggs, and Adam Meyerson. Simultaneous Source Location. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2004.
Nikhil Bansal, Avrim Blum, Shuchi Chawla, and Adam Meyerson. Approximation Algorithms for Deadline-TSP. ACM Symposium on Theory of Computing (STOC) 2004.
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local Search Heuristics for k-median and Facility Location Problems. SIAM Journal of Computing 33(3), 2004 (conference version in STOC 2001).
Adam Meyerson, Liadan O'Callaghan, and Serge Plotkin. A k-median Algorithm with Running Time Independent of Data Size. Journal of Machine Learning, Special Issue on Theoretical Advances in Data Clustering (MLJ) 2004.
Lisa Fleischer, Adam Meyerson, Iraj Saniee, Bruce Shepherd, and Aravind Srinivasan. A Scalable Algorithm for the Minimum Expected Cost Restorable Flow Problem. CORC Tech Report TR-2003-10.
Konstantin Andreev, Bruce Maggs, Adam Meyerson, and Ramesh Sitaraman. Designing Overlay Multicast Networks for Streaming. ACM Symposium on Parallellism in Algorithms and Architectures (SPAA) 2003.
Sudipto Guha, Adam Meyerson, and Kamesh Munagala. A constant factor approximation algorithm for the fault-tolerant facility location problem. Journal of Algorithms 48(2), 2003 (conference version in SODA 2001).
Zoe Abrams, Adam Meyerson, Kamesh Munagala, and Serge Plotkin. The Integrality Gap of Capacitated Facility Location. CMU-CS-02-199, December 2002.
Adam Meyerson, Liadan O'Callaghan, and Serge Plotkin. Adventures in Ultra-Small-Space Clustering. CMU-CS-02-193, December 2002.
Adam Meyerson. Profit-Earning Facility Location. ACM Symposium on Theory of Computing (STOC) 2001.
Sudipto Guha, Adam Meyerson, and Kamesh Munagala. Improved Combinatorial Algorithms for Single Sink Edge Installation Problems. ACM Symposium on Theory of Computing (STOC) 2001.
Adam Meyerson, Kamesh Munagala, and Serge Plotkin. Web Caching using Access Statistics. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2001.
Zoe Abrams, Jochen Konemann, Adam Meyerson, Kamesh Munagala, and Serge Plotkin. Facility Location with Interference. GSIA Working Paper #2001-E23, 2001.
Adam Meyerson, Kamesh Munagala, and Serge Plotkin. Cost-Distance: Two-Metric Network Design. IEEE Symposium on Foundations of Computer Science (FOCS) 2000.
Sudipto Guha, Adam Meyerson, and Kamesh Munagala. Hierarchical Placement and Network Design Problems. IEEE Symposium on Foundations of Computer Science (FOCS) 2000.

Online (and Streaming) Algorithms Publications

Aaron Cote, Adam Meyerson, and Laura Poplawski. Randomized K-Server on Hierarchical Binary Trees. ACM Symposium on Theory of Computing (STOC) 2008.
Adam Meyerson, Akash Nanavati, and Laura Poplawski. Randomized Online Algorithms for Minimum Metric Bipartite Matching. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2006.
Adam Meyerson. The Parking Permit Problem. IEEE Symposium on Foundations of Computer Science (FOCS) 2005.
Adam Meyerson. Online Algorithms for Network Design. ACM Symposium on Parallellism in Algorithms and Architectures (SPAA) 2004.
Nikhil Bansal, Avrim Blum, Shuchi Chawla, and Adam Meyerson. Online Oblivious Routing. ACM Symposium on Parallellism in Algorithms and Architectures (SPAA) 2003.
Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O'Callaghan. Clustering Data Streams: Theory and Practice. IEEE Transactions on Data and Knowledge Engineering (TDKE), Volume 15, 2003.
Liadan O'Callaghan, Nina Mishra, Adam Meyerson, Sudipto Guha, and Rajeev Motwani. Streaming-Data Algorithms for High-Quality Clustering. IEEE International Conference on Data Engineering (ICDE) 2002.
Adam Meyerson. Online Facility Location. IEEE Symposium on Foundations of Computer Science (FOCS) 2001.
Adam Meyerson, Kamesh Munagala, and Serge Plotkin. Designing Networks Incrementally. IEEE Symposium on Foundations of Computer Science (FOCS) 2001.
Ashish Goel, Adam Meyerson, and Serge Plotkin. Distributed Admission Control, Scheduling, and Routing with Stale Information. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2001.

Game Theory and Resource Allocation Publications

Gunes Ercal, Rafit Izhak-Ratzin, Rupak Majumdar, and Adam Meyerson. Frugal Routing on Wireless Ad-Hoc Networks. International Symposium on Algorithmic Game Theory (SAGT) 2008.
David Kempe, Adam Meyerson, Nainesh Solanki, and Ramnath Chellappa. Pricing of Partially Compatible Products. ACM Conference on Electronic Commerce (EC) 2007.
Sven Koenig, Craig Rovey, Michael Lagoudakis, Evangelos Markakis, David Kempe, Pinar Keskinocak, Anton Kleywegt, Adam Meyerson, and Sonal Jain. The Power of Sequential Single-Item Auctions for Agent Coordination. AAAI 2006.
Ashish Goel and Adam Meyerson. Simultaneous Optimization via Approximate Majorization for Concave Profits or Convex Costs. Algorithmica 44(4), 2006.
Sven Koenig, Michail Lagoudakis, Vangelis Markakis, David Kempe, Pinar Keskinocak, Anton Kleywegt, Craig Tovey, Adam Meyerson, and Sonal Jain. Auction-Based Multi-Robot Routing. Robotics: Science and Systems 2005.
Ashish Goel, Adam Meyerson, and Serge Plotkin. Approximate Majorization and Fair Online Load Balancing. ACM Transactions on Algorithms 1(2), 2005 (conference version in SODA 2001).
Baruch Awerbuch, Yossi Azar, and Adam Meyerson. Reducing Truth-telling Online Mechanisms to Online Optimization. ACM Symposium on Theory of Computing (STOC) 2003.
Rishi Bhargava, Ashish Goel, and Adam Meyerson. Using Approximate Majorization to Characterize Protocol. ACM SIGMETRICS 2001.
Ashish Goel, Adam Meyerson, and Serge Plotkin. Combining Fairness with Throughput: Online Routing with Multiple Objectives. Journal of Computer and System Sciences, Issue 63, 2001 (conference version in STOC 2000).

Metric Embedding Publications

Douglas Carroll, Ashish Goel, and Adam Meyerson. Embedding Bounded Bandwidth Graphs into L1. International Colloquium on Automata, Languages, and Programming (ICALP) 2006.
Tomas Feder, Adam Meyerson, Rajeev Motwani, Liadan O'Callaghan, and Rina Pinagrahy. Representing Graph Metrics with Fewest Edges. International Symposium on Theoretical Aspects of Computer Science (STACS) 2003.

Additional Publications

Mohit Lad, Dan Massey, Adam Meyerson, Akash Nanavati, and Lixia Zhang. Minimum Failure Explanations for Path Vector Routing. Journal of Combinatorial Optimization, special issue on Communication Networks and Internet Applications, 2006.
Adam Meyerson and Ryan Williams. On the Complexity of Optimal K-Anonymity. ACM Symposium on Principles of Database Systems (PODS) 2004.