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
Additional Publications