Preprints

• J. Komatovic, J. Neu, and, T. Roughgarden, Toward Optimal-Complexity Hash-Based Asynchronous MVBA with Optimal Resilience.
• A. Komo, S. D. Kominers, and, T. Roughgarden, Shill-Proof Auctions. (Tweetstorm (in PDF))
• A. Lewis-Pye and T. Roughgarden, Permissionless Consensus. (Recursive tweetstorm (in PDF)) (45-minute and two-hour tutorials by Andy)

2025

• N. Durvasula and, T. Roughgarden, Robust Restaking Networks, ITCS '25. (Tweetstorm (in PDF)) (Talks by Naveen and Tim)

2024

• M. Bahrani, P. Garimidi, and T. Roughgarden, Transaction Fee Mechanism Design in a Post-MEV World, AFT '24. (Tweetstorm ((in PDF)) (a16z blog post) (Related talk by Pranav)
  • Subsumes the earlier working paper with the title Transaction Fee Mechanism Design with Active Block Producers, presented at the 4th FC Workshop on Decentralized Finance.
• E. Budish, A. Lewis-Pye, and T. Roughgarden, The Economic Limits of Permissionless Consensus, EC '24. (Tweetstorm (in PDF))
  • Talks by Andy; Tim (short); Tim (long); CBER Panel)
• H. Chung, T. Roughgarden, and E. Shi, Collusion-Resilience in Transaction Fee Mechanism Design, EC '24. (Tweetstorm (in PDF)) (Hao's talk)
• W. Brown, C. H. Papadimitriou, and T. Roughgarden, Online Stackelberg Optimization via Nonlinear Control, COLT '24.
• M. Bahrani, P. Garimidi, and T. Roughgarden, Centralization in Block Building and Proposer-Builder Separation, FC '24. (Pranav's tweetstorm (in PDF)) (Pranav's talk)
• J. Milionis, C. C. Moallemi, and T. Roughgarden, Automated Market Making and Arbitrage Profits in the Presence of Fees, FC '24. (Talk by Ciamac) (Ciamac's tweetstorm (in PDF))
• J. Milionis, C. C. Moallemi, and T. Roughgarden, A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers, ITCS '24. (Jason's talk)

2023

• D. R. Graham, K. Leyton-Brown, and T. Roughgarden, Utilitarian Algorithm Configuration, NeurIPS '23. (Devon's talk)
• E. Neyman and T. Roughgarden, No-Regret Learning with Unbounded Losses: The Case of Logarithmic Pooling, NeurIPS '23. (Eric's talk) (Related talk by Tim)
• M. Bahrani, P. Garimidi, and T. Roughgarden, When Bidders Are DAOs, AFT '23. (Pranav's talk) (Pranav's tweetstorm (in PDF))
• D. R. Graham, K. Leyton-Brown, and T. Roughgarden, Formalizing Preferences Over Runtime Distributions, ICML '23. (Devon's talk) (Talk by Kevin)
• J. Milionis, C. C. Moallemi, and T. Roughgarden, Complexity-Approximation Trade-offs in Exchange Mechanisms: AMMs vs. LOBs, FC '23. (Jason's tweetstorm (in PDF)) (Related talk)
• A. Lewis-Pye and T. Roughgarden, Byzantine Generals in the Permissionless Setting, FC '23. (Related talks by Andy Tim)
  • Precursor (cite as arXiv:2006.10698): Resource Pools and the CAP Theorem.

2022

• J. Milionis, C. C. Moallemi, T. Roughgarden, and A. L. Zhang, Automated Market Making and Loss-Versus-Rebalancing, full version of abstract presented at DeFi@CCS '22.
  • (Jason's tweetstorm (in PDF)) (a16z blog post) (Talks by Jason Ciamac Tim Anthony) (LVR in 3 minutes) (LVR for practitioners)
• E. Neyman and T. Roughgarden, Are You Smarter Than a Random Expert? The Robust Aggregation of Substitutable Signals, EC '22. (Eric's talk)
• E. Neyman and T. Roughgarden, Strictly Proper Contract Functions Can Be Arbitrage-Free, AAAI '22.
• B. Behera, E. Husic, S. Jain, T. Roughgarden, and C. Seshadhri, FPT Algorithms for Finding Near-Cliques in c-Closed Graphs, ITCS '22. (Related talk)

2021

• N. Haghtalab, T. Roughgarden, and A. Shetty, Smoothed Analysis with Adaptive Adversaries, FOCS '21/JACM '24. (Related talk) (Abhishek's talk)
• A. Lewis-Pye and T. Roughgarden, How Does Blockchain Security Dictate Blockchain Implementation?, CCS '21. (Andy's talk) (Related talk by Tim) (Related tweetstorm (in PDF))
• E. Neyman and T. Roughgarden, From Proper Scoring Rules to Max-Min Optimal Forecast Aggregation, EC '21/OR '23. (Talk by Eric) (Related talk by Tim)
• T. Roughgarden, Transaction Fee Mechanism Design, EC '21/JACM '24. (SIGecom Exchanges version) (60-minute talk) (30-minute talk)
• T. Roughgarden and C. Shikhelman, Ignore the Extra Zeroes: Variance-Optimal Mining Pools, FC '21. (Clara's talk)

2020

• T. Roughgarden, Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559, December 2020. (Tweetstorm (in PDF)) (Ethereum meetup talk and Epicenter podcast)
• N. Haghtalab, T. Roughgarden, and A. Shetty, Smoothed Analysis of Online and Differentially Private Learning, NeurIPS '20. (Nika's talk)
• R. Gupta and T. Roughgarden, Data-Driven Algorithm Design, Communications of the ACM, June 2020. ("Research highlights" version of the ITCS '16 paper below.) (Talk)
• P. Duetting, T. Roughgarden, and I. Talgam-Cohen, The Complexity of Contracts, SODA '20/SICOMP '21. (Related tutorial by Paul and Inbal)
• T. Roughgarden and C. Seshadhri, Distribution-Free Models of Social Networks, Chapter 28 in Beyond the Worst-Case Analysis of Algorithms. (Related talk)
• T. Roughgarden, Distributional Analysis, Chapter 8 in Beyond the Worst-Case Analysis of Algorithms.
• T. Roughgarden, Resource Augmentation, Chapter 4 in Beyond the Worst-Case Analysis of Algorithms. (Related lecture)
• T. Roughgarden, Introduction (to Beyond Worst-Case Analysis), Chapter 1 in Beyond the Worst-Case Analysis of Algorithms. (Related course)
• T. Roughgarden, Complexity Theory, Game Theory, and Economics (The Barbados Lectures), Foundations and Trends in TCS. (Preprint)

2019

• X. Chen, C. Papadimitriou, and T. Roughgarden, An Axiomatic Approach to Block Rewards, AFT '19. (Related talk)
• P. Duetting, T. Roughgarden, and I. Talgam-Cohen, Simple versus Optimal Contracts, EC '19. (Talk by Inbal) (Related tutorial by Paul and Inbal)
• V. Chatziafratis, T. Roughgarden, and J. R. Wang, On the Computational Power of Online Gradient Descent, COLT '19. (Talk by Vaggos)
• T. Roughgarden, Complexity-Theoretic Barriers in Economics, The Future of Economic Design. (Related talk)
• T. Roughgarden and I. Talgam-Cohen, Approximately Optimal Mechanism Design, Annual Reviews of Economics.
• T. Roughgarden, Beyond Worst-Case Analysis, Communications of the ACM. (Related course)
• G. Barmpalias, N. Huang, A. Lewis-Pye, A. Li, X. Li, Y. Pan, and T. Roughgarden, The Idemetric Property: When Most Distances Are (Almost) the Same, Proceedings of the Royal Society A.
• B. Plaut and T. Roughgarden, Communication Complexity of Discrete Fair Division, SODA '19/SICOMP '20. (Related talk)

2018

• R. Niazadeh, T. Roughgarden, and J. R. Wang, Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization, NeurIPS '18/JMLR '20.
• T. Ezra, M. Feldman, T. Roughgarden, and W. Suksompong, Pricing Identical Items, WINE '18/TEAC '20.
• J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein, Finding Cliques in Social Networks: A New Distribution-Free Model, ICALP '18/SICOMP '20. (Related talk)
• T. Roughgarden and J. R. Wang, An Optimal Algorithm for Online Unconstrained Submodular Maximization, COLT '18. (Related talk)
• B. Plaut and T. Roughgarden, Almost Envy-Freeness with General Valuations, SODA '18/SIDMA '20. (Related talk)

2017

• T. Roughgarden and O. Schrijvers, Online Prediction with Selfish Experts, NIPS '17. (Talk by Okke)
• V. Chatziafratis, T. Roughgarden, and J. Vondrak, Stability and Recovery for Independence Systems, ESA '17.
• T. Roughgarden, I. Talgam-Cohen, and J. Vondrak, When Are Welfare Guarantees Robust?, APPROX '17.
• V. Gkatzelis, E. Markakis, and T. Roughgarden, Deferred-Acceptance Auctions for Multiple Levels of Service, EC '17. (Talk by Vasilis)
• R. Colini-Baldeschi, P. Goldberg, B. de Keijzer, S. Leonardi, T. Roughgarden, and S. Turchetta, Approximately Efficient Two-Sided Combinatorial Auctions, EC '17. (Talk by Stefano T)
• T. Roughgarden, V. Syrgkanis, and E. Tardos, The Price of Anarchy in Auctions (survey), Journal of Artificial Intelligence Research. (Related talk)

2016

• Y. Chen, A. Ghosh, M. Kearns, T. Roughgarden, and J. Wortman Vaughan, Mathematical Foundations for Social Computing, Communications of the ACM, December 2016. (Preprint)
• T. Roughgarden and O. Weinstein, On the Communication Complexity of Approximate Fixed Points, FOCS '16. (Talk by Omri)
• T. Roughgarden and J. R. Wang, The Complexity of the k-Means Method, ESA '16.
• T. Roughgarden and O. Schrijvers, Ironing in the Dark , EC '16.
• T. Roughgarden and J. R. Wang, Minimizing Regret with Multiple Reserves, EC '16/TEAC '19.
• T. Roughgarden, S. Vassilvitskii, and J. R. Wang, Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation), SPAA '16/JACM '18.
• J. Morgenstern and T. Roughgarden, Learning Simple Auctions, COLT '16. (Jamie's talk)
• M. Feldman, N. Immorlica, B. Lucier, T. Roughgarden, and V. Syrgkanis, The Price of Anarchy in Large Games, STOC '16. (Related talk by Brendan)
• T. Roughgarden, Communication Complexity (for Algorithm Designers), Foundations and Trends in TCS. (arXiv version)
• O. Schrijvers, J. Bonneau, D. Boneh, and T. Roughgarden, Incentive Compatibility of Bitcoin Mining Pool Reward Functions, FC '16.
• R. Gupta and T. Roughgarden, A PAC Approach to Application-Specific Algorithm Selection, ITCS '16/SICOMP '17. (Talk)

2015

• J. Morgenstern and T. Roughgarden, The Pseudo-Dimension of Near-Optimal Auctions, NIPS '15. (Related talk)
• A. Globerson, T. Roughgarden, D. Sontag, and C. Yildirim, How Hard Is Inference for Structured Prediction? , ICML '15. (longer arXiv version) (Talk)
• T. Roughgarden and I. Talgam-Cohen, Why Prices Need Algorithms, EC '15.
• P. Gopalan, N. Nisan, and T. Roughgarden, Public Projects, Boolean Functions, and the Borders of Border's Theorem, EC '15/TEAC '18. (Talk by Noam)
• Z. Huang, Y. Mansour, and T. Roughgarden, Making the Most of Your Samples, EC '15/SICOMP '18.

2014

• V. Gkatzelis, K. Kollias, and T. Roughgarden, Optimal Cost-Sharing in General Resource Selection Games, WINE '14/OR '16.
• T. Roughgarden, Approximately Optimal Mechanism Design: Motivation, Examples, and Lessons Learned, SIGEcom Exchanges, 2014.
• T. Roughgarden, Barriers to Near-Optimal Equilibria, FOCS '14. FOCS talk (Lecture notes)
• T. Roughgarden and O. Schrijvers, Network Cost-Sharing without Anonymity, SAGT '14/TEAC '16.
• J. Hsu, A. Roth, T. Roughgarden, and J. Ullman, Privately Solving Linear Programs, ICALP '14.
• P. Duetting, V. Gkatzelis, and T. Roughgarden, The Performance of Deferred-Acceptance Auctions, EC '14/MOR '17.
• P. Duetting, T. Roughgarden, and I. Talgam-Cohen, Modularity and Greed in Double Auctions, EC '14/GEB '17.
• J. Hsu, Z. Huang, A. Roth, T. Roughgarden, and Z. S. Wu, Private Matchings and Allocations, STOC '14/SICOMP '16.
• R. Cole and T. Roughgarden, The Sample Complexity of Revenue Maximization, STOC '14.
• R. Gupta, T. Roughgarden, and C. Seshadhri, Decompositions of Triangle-Dense Graphs, ITCS '14/SICOMP '16. (Lecture notes) (Related talk)

2013

• T. Roughgarden and M. Kearns, Marginals-to-Models Reducibility, NIPS '13.
• T. Roughgarden and I. Talgam-Cohen, Optimal and Near-Optimal Mechanism Design with Interdependent Values, EC '13/TEAC '16. (Talk by Inbal)
• S. Bhattacharya, E. Koutsoupias, J. Kulkarni, S. Leonardi, T. Roughgarden, and X. Xu, Prior-Free Multi-Unit Auctions with Ordered Bidders, EC '13 (full version, combined with STOC '12 paper, as of May '14).

2012

• K. Bhawalkar and T. Roughgarden, Simultaneous Single-Item Auctions, WINE '12.
• K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma, Preventing Unraveling in Social Networks: The Anchored k-Core Problem, ICALP '12/SIDMA '15.
• T. Roughgarden, Intrinsic Robustness of the Price of Anarchy, Communications of the ACM, July 2012. ("Research highlights" version of STOC '09 paper.) Also: preprint and video.
• T. Roughgarden and E. Tardos, Do Externalities Degrade GSP's Efficiency?, Ad Auctions '12.
• T. Roughgarden, The Price of Anarchy in Games of Incomplete Information, EC '12/TEAC '14. (Related talk)
• T. Roughgarden, I. Talgam-Cohen, and Q. Yan, Robust Auctions for Revenue via Enhanced Competition, EC '12/OR '20. The conference version, with the title Supply-Limiting Mechanisms, has some additional results.
• I. Abraham, M. Babaioff, S. Dughmi, and T. Roughgarden, Combinatorial Auctions with Restricted Complements, EC '12.
• S. Leonardi and T. Roughgarden, Prior-Free Auctions with Ordered Bidders, STOC '12. Journal version, combined with EC '13 paper above (as of May '14).
• A. Badanidiyuru, S. Dobzinski, H. Fu, R. D. Kleinberg, N. Nisan and T. Roughgarden, Sketching Valuation Functions, SODA '12.

2011

• U. Nadav, R. Johari, and T. Roughgarden, Uncoupled Potentials for Proportional Allocation Markets, CDC '11.
• S. Dughmi, T. Roughgarden, and Q. Yan, Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding, STOC '11/JACM '16. (Lecture notes)
• K. Kollias and T. Roughgarden, Restoring Pure Equilibria to Weighted Congestion Games, ICALP '11/TEAC '15.
• R. Kumar, J. Talton, S. Ahmad, T. Roughgarden, and S. Klemmer, Flexible Tree Matching, IJCAI '11.
• K. Bhawalkar and T. Roughgarden, Welfare Guarantees for Combinatorial Auctions with Item Bidding, SODA '11. (Related talk)
• T. Roughgarden and F. Schoppmann, Local Smoothness and the Price of Anarchy in Splittable Congestion Games, SODA '11/JET '14.

2010

• U. Nadav and T. Roughgarden, The Limits of Smoothness: A Primal-Dual Framework for Price of Anarchy Bounds, WINE '10.
• J. Marden and T. Roughgarden, Generalized Efficiency Bounds in Distributed Resource Allocation, CDC '10/IEEE TAC '14.
• S. Dughmi and T. Roughgarden, Black-Box Randomized Reductions in Algorithmic Mechanism Design, FOCS '10/SICOMP '14.
• T. Roughgarden, Algorithmic Game Theory, Communications of the ACM, July 2010. Preprint
  • This is a revised and abridged version of the TCS '08 survey below.
• K. Bhawalkar, M. Gairing, and T. Roughgarden, Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness, ESA '10/TEAC '14.
• P. Dhangwatnotai, T. Roughgarden, and Q. Yan, Revenue Maximization with a Single Sample, EC '10/GEB '14.
• M. Babaioff and T. Roughgarden, Equilibrium Efficiency and Price Complexity in Sponsored Search Auctions, Workshop on Ad Auctions.
• A. Roth and T. Roughgarden, Interactive Privacy via the Median Mechanism, STOC '10.
• T. Roughgarden, Computing Equilibria: A Computational Complexity Perspective, invited survey for Economic Theory.

2009

• J. D. Hartline and T. Roughgarden, Simple versus Optimal Mechanisms, EC '09. (Related talk)
• S. Dughmi, T. Roughgarden, and M. Sundararajan, Revenue Submodularity, EC '09/Theory of Computing '12.
  • Section 6 subsumes the working paper Is Efficiency Expensive?, presented at the 3rd Workshop on Sponsored Search, 2007.
• D. Mosk-Aoyama and T. Roughgarden, Worst-Case Efficiency Analysis of Queueing Disciplines, ICALP '09.
• T. Roughgarden, Intrinsic Robustness of the Price of Anarchy, STOC '09/JACM '15. See also CACM version above. (Related talk)
• A. Ghosh, T. Roughgarden, and M. Sundararajan, Universally Utility-Maximizing Privacy Mechanisms, STOC '09/SICOMP '12.
• A. Motskin, T. Roughgarden, P. Skraba, and L. Guibas, Lightweight Coloring and Desynchronization for Networks, INFOCOM '09.

2008

• P. Dhangwatnotai, S. Dobzinski, S. Dughmi, and T. Roughgarden, Truthful Approximation Schemes for Single-Parameter Agents, FOCS '08/SICOMP '11.
• T. Roughgarden, An Algorithmic Game Theory Primer, TCS '08 (invited survey).
• J. D. Hartline and T. Roughgarden, Optimal Mechanism Design and Money Burning, STOC '08.
  • For a more recent (2016) version with a different emphasis and some new results, see Optimal Platform Design.
• S. Dobzinski, A. Mehta, T. Roughgarden, and M. Sundararajan, Is Shapley Cost Sharing Optimal?, SAGT '08/GEB '17.
• S. Chawla and T. Roughgarden, Bertrand Competition in Networks, SAGT '08.
• H. Chen, T. Roughgarden, and G. Valiant, Designing Networks with Good Equilibria, SODA '08/SICOMP '10.
• R. Krauthgamer and T. Roughgarden, Metric Clustering via Consistent Labeling, SODA '09/Theory of Computing '11.

2007

• N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (eds.), Algorithmic Game Theory, Cambridge University Press.
• T. Roughgarden, Routing Games, Chapter 18 in Algorithmic Game Theory.
• T. Roughgarden and E. Tardos, Introduction to the Inefficiency of Equilibria, Chapter 17 in Algorithmic Game Theory.
• D. Mosk-Aoyama, T. Roughgarden, and D. Shah, Fully Distributed Algorithms for Convex Optimization, DISC '07/SIAM J on Optimization '10.
• M. Haviv and T. Roughgarden, The Price of Anarchy in an Exponential Multi-Server, Operations Research Letters.
• T. Roughgarden, Selfish Routing and the Price of Anarchy (Survey), OPTIMA #74.
• T. Roughgarden and M. Sundararajan, Optimal Efficiency Guarantees for Network Design Mechanisms, IPCO '07.
• A. Mehta, T. Roughgarden, and M. Sundararajan, Beyond Moulin Mechanisms, EC '07/GEB '09.

2006

• S. Chawla, T. Roughgarden, and M. Sundararajan, Optimal Cost-Sharing Mechanisms for Steiner Forest Problems, WINE '06.
• S. Chawla and T. Roughgarden, Single-Source Stochastic Routing, APPROX '06.
• T. Roughgarden, Potential Functions and the Inefficiency of Equilibria (Survey), ICM '06.
• H. Chen and T. Roughgarden, Network Design with Weighted Players, SPAA '06/Theory of Computing Systems '09.
• T. Roughgarden and M. Sundararajan, Quantifying Inefficiency in Cost-Sharing Mechanisms, STOC '06/JACM '09.
• G. Valiant and T. Roughgarden, Braess's Paradox in Large Random Graphs, EC '06/Random Structures and Algorithms '10.
• R. Cole, Y. Dodis, and T. Roughgarden, Bottleneck Links, Variable Demand, and the Tragedy of the Commons, SODA '06/Networks '12.
• M. Saha, G. Sanchez-Ante, T. Roughgarden, and J.C. Latombe, Planning Tours of Robotic Arms Among Partitioned Goals, International Journal of Robotics Research.

2005

• T. Roughgarden. Selfish Routing and the Price of Anarchy, MIT Press.
• M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden, Routers with Very Small Buffers, ACM Computer Communication Review. INFOCOM '06 version.
• H. Lin, T. Roughgarden, E. Tardos, and A. Walkover, Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability, ICALP '05/SIDMA '11.
  • This is the full version with the new title Stronger Bounds on Braess's Paradox and the Maximum Latency of Selfish Routing and includes both SODA 04 papers below.
• T. Roughgarden, Selfish Routing with Atomic Players, SODA '05. Erratum
• C. Papadimitriou and T. Roughgarden, Computing Correlated Equilibria in Multi-Player Games, SODA '05/JACM '08. Addendum

2004

• E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, FOCS '04/SICOMP '08.
• T. Roughgarden and E. Tardos, Bounding the Inefficiency of Equilibria in Nonatomic Congestion Games, Games and Economic Behavior.
• T. Roughgarden, The Maximum Latency of Selfish Routing, SODA '04.
• H. Lin, T. Roughgarden, and E. Tardos, A Stronger Bound on Braess's Paradox, SODA '04.
  • Journal version of these two SODA papers, combined with the ICALP '05 paper above, appeared in SIDMA '11.

2003

• A. Gupta, A. Kumar, M. Pal, and T. Roughgarden, Approximation Via Cost Sharing, FOCS '03.
  • Journal version, combined with STOC '03 paper below. Appears in JACM '07.
• A. Gupta, A. Kumar, and T. Roughgarden, Simpler and Better Approximation Algorithms for Network Design, STOC '03. (Full version combined with FOCS '03 paper, above.)
• R. Cole, Y. Dodis, and T. Roughgarden, Pricing Network Edges for Heterogeneous Selfish Users, STOC '03.
• R. Cole, Y. Dodis, and T. Roughgarden, How Much Can Taxes Help Selfish Routing?, EC '03/JCSS '06.
  • Survey of EC '03 and STOC '03 pricing papers, presented at P2PECON '03.

2002

• T. Roughgarden, Selfish Routing, PhD Thesis, Cornell University.
• A. Kumar, A. Gupta, and T. Roughgarden, A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem, FOCS '02.
  • No journal version of this paper is planned, although the algorithm and analysis were simplified and extended in a STOC '09 paper of Gupta and Kumar.
• T. Roughgarden, The Price of Anarchy is Independent of the Network Topology, STOC '02/JCSS '03.
• A. Hoffman, K. Jenkins, and T. Roughgarden, On a Game in Directed Graphs, IPL '02.
• T. Roughgarden, How Unfair is Optimal Routing?, SODA '02.

2001

• T. Roughgarden, Designing Networks for Selfish Users is Hard, FOCS '01/JCSS '06.
• T. Roughgarden, Stackelberg Scheduling Strategies, STOC '01/SICOMP '04.
• F. Chudak, T. Roughgarden, and D. Williamson, Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation, IPCO '01/Mathematical Programming '04.

2000

• T. Roughgarden and E. Tardos, How Bad is Selfish Routing?, FOCS '00/JACM '02.

Home