☰

Timothy A. Roughgarden - Publications

Affiliations: 
2004-2018 Computer Science Stanford University, Palo Alto, CA 
 2019- Columbia University, New York, NY 
Website:
http://timroughgarden.org/
Tree Info Similar researchers PubMed Report error

70 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Plaut B, Roughgarden T. Almost Envy-Freeness with General Valuations Siam Journal On Discrete Mathematics. 34: 1039-1068. DOI: 10.1137/19M124397X  0.308
2020 Fox J, Roughgarden T, Seshadhri C, Wei F, Wein N. Finding Cliques in Social Networks: A New Distribution-Free Model Siam Journal On Computing. 49: 448-464. DOI: 10.1137/18M1210459  0.331
2019 Barmpalias G, Huang N, Lewis-Pye A, Li A, Li X, Pan Y, Roughgarden T. The idemetric property: when most distances are (almost) the same. Proceedings. Mathematical, Physical, and Engineering Sciences. 475: 20180283. PMID 30853838 DOI: 10.1098/Rspa.2018.0283  0.398
2019 Roughgarden T, Talgam-Cohen I. Approximately Optimal Mechanism Design Annual Review of Economics. 11: 355-381. DOI: 10.1146/Annurev-Economics-080218-025607  0.39
2018 Roughgarden T, Vassilvitskii S, Wang JR. Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation) Journal of the Acm. 65: 41. DOI: 10.1145/3232536  0.327
2017 Roughgarden T, Syrgkanis V, Tardos É. The price of anarchy in auctions Journal of Artificial Intelligence Research. 59: 59-101. DOI: 10.1613/Jair.5272  0.672
2017 Gupta R, Roughgarden T. A PAC Approach to Application-Specific Algorithm Selection Siam Journal On Computing. 46: 992-1017. DOI: 10.1137/15M1050276  0.302
2016 Roughgarden T. Communication Complexity for Algorithm Designers Foundations and Trends in Theoretical Computer Science. 11: 217-404. DOI: 10.1561/0400000076  0.302
2016 Gkatzelis V, Kollias K, Roughgarden T. Optimal Cost-Sharing in General Resource Selection Games Operations Research. 64: 1230-1238. DOI: 10.1287/Opre.2016.1512  0.484
2016 Dughmi S, Roughgarden T, Yan Q. Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding Journal of the Acm. 63: 30. DOI: 10.1145/2908735  0.405
2016 Hsu J, Huang Z, Roth A, Roughgarden T, Wu ZS. Private Matchings and Allocations Siam Journal On Computing. 45: 1953-1984. DOI: 10.1137/15100271X  0.352
2016 Gupta R, Roughgarden T, Seshadhri C. Decompositions of triangle-dense graphs Siam Journal On Computing. 45: 197-215. DOI: 10.1137/140955331  0.304
2015 Roughgarden T, Talgam-Cohen I. Why prices need algorithms Ec 2015 - Proceedings of the 2015 Acm Conference On Economics and Computation. 19-36. DOI: 10.1145/2904104.2904109  0.4
2015 Roughgarden T. Intrinsic robustness of the price of anarchy Journal of the Acm. 62. DOI: 10.1145/2806883  0.431
2015 Roughgarden T. Approximately optimal mechanism design: motivation, examples, and lessons learned Sigecom Exchanges. 13: 4-20. DOI: 10.1145/2728732.2728733  0.377
2015 Roughgarden T. The price of anarchy in games of incomplete information Acm Transactions On Economics and Computation. 3. DOI: 10.1145/2325713.2325716  0.357
2015 Bhawalkar K, Kleinberg J, Lewi K, Roughgarden T, Sharma A. Preventing unraveling in social networks: The anchored k-core problem Siam Journal On Discrete Mathematics. 29: 1452-1475. DOI: 10.1137/14097032X  0.385
2015 Roughgarden T, Schoppmann F. Local smoothness and the price of anarchy in splittable congestion games Journal of Economic Theory. 156: 317-342. DOI: 10.1016/J.Jet.2014.04.005  0.474
2015 Dhangwatnotai P, Roughgarden T, Yan Q. Revenue maximization with a single sample Games and Economic Behavior. 91: 318-333. DOI: 10.1016/J.Geb.2014.03.011  0.377
2014 Dütting P, Gkatzelis V, Roughgarden T. The performance of deferred-acceptance auctions Ec 2014 - Proceedings of the 15th Acm Conference On Economics and Computation. 187-204. DOI: 10.1287/Moor.2016.0835  0.434
2014 Dughmi S, Roughgarden T. Black-box randomized reductions in algorithmic mechanism design Siam Journal On Computing. 43: 312-336. DOI: 10.1137/110843654  0.393
2014 Marden JR, Roughgarden T. Generalized efficiency bounds in distributed resource allocation Ieee Transactions On Automatic Control. 59: 571-584. DOI: 10.1109/TAC.2014.2301613  0.316
2014 Roughgarden T. Barriers to near-optimal Equilibria Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 71-80. DOI: 10.1109/FOCS.2014.16  0.39
2014 Dütting P, Roughgarden T, Talgam-Cohen I. Modularity and greed in double auctions Ec 2014 - Proceedings of the 15th Acm Conference On Economics and Computation. 241-258. DOI: 10.1016/J.Geb.2017.06.008  0.4
2014 Roughgarden T, Schrijvers O. Network cost-sharing without anonymity Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8768: 134-145.  0.408
2014 Gkatzelis V, Kollias K, Roughgarden T. Optimal cost-sharing in weighted congestion games Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8877: 72-88.  0.356
2013 Roughgarden T, Talgam-Cohen I. Optimal and near-optimal mechanism design with interdependent values Proceedings of the Acm Conference On Electronic Commerce. 767-784.  0.3
2012 Ghosh A, Roughgarden T, Sundararajan M. Universally utility-maximizing privacy mechanisms Siam Journal On Computing. 41: 1673-1693. DOI: 10.1137/09076828X  0.593
2012 Cole R, Dodis Y, Roughgarden T. Bottleneck links, variable demand, and the tragedy of the commons Networks. 60: 194-203. DOI: 10.1002/Net.21458  0.49
2011 Lin H, Roughgarden T, Tardos E, Walkover A. Stronger bounds on braess's paradox and the maximum latency of selfish routing Siam Journal On Discrete Mathematics. 25: 1667-1686. DOI: 10.1137/090769600  0.691
2011 Dhangwatnotai P, Dobzinski S, Dughmi S, Roughgarden T. Truthful approximation schemes for single-parameter agents Siam Journal On Computing. 40: 915-933. DOI: 10.1137/080744992  0.323
2011 Kollias K, Roughgarden T. Restoring pure equilibria to weighted congestion games Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6756: 539-551. DOI: 10.1007/978-3-642-22012-8_43  0.372
2010 Mosk-Aoyama D, Roughgarden T, Shah D. Fully distributed algorithms for convex optimization problems Siam Journal On Optimization. 20: 3260-3279. DOI: 10.1137/080743706  0.414
2010 Chen HL, Roughgarden T, Valiant G. Designing network protocols for good equilibria Siam Journal On Computing. 39: 1799-1832. DOI: 10.1137/08072721X  0.541
2010 Valiant G, Roughgarden T. Braess's Paradox in large random graphs Random Structures and Algorithms. 37: 495-515. DOI: 10.1002/Rsa.V37:4  0.364
2009 Hartline JD, Roughgarden T. Simple versus optimal mechanisms Proceedings of the Acm Conference On Electronic Commerce. 225-234. DOI: 10.1145/1598780.1598785  0.411
2009 Roughgarden T, Sundararajan M. Quantifying inefficiency in cost-sharing mechanisms Journal of the Acm. 56. DOI: 10.1145/1538902.1538907  0.643
2009 Mehta A, Roughgarden T, Sundararajan M. Beyond Moulin mechanisms Games and Economic Behavior. 67: 125-155. DOI: 10.1016/J.Geb.2008.06.005  0.64
2009 Chen HL, Roughgarden T. Network design with weighted players Theory of Computing Systems. 45: 302-324. DOI: 10.1007/S00224-008-9128-8  0.491
2009 Dughmi S, Roughgarden T, Sundararajan M. Revenue submodularity Lecture Notes of the Institute For Computer Sciences, Social-Informatics and Telecommunications Engineering. 14: 89-91. DOI: 10.1007/978-3-642-03821-1_13  0.525
2008 Krauthgamer R, Roughgarden T. Metric clustering via consistent labeling Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 809-818. DOI: 10.4086/Toc.2011.V007A005  0.352
2008 Chawla S, Roughgarden T. Bertrand competition in networks Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4997: 70-82. DOI: 10.1145/1598780.1598790  0.414
2008 Papadimitriou CH, Roughgarden T. Computing correlated equilibria in multi-player games Journal of the Acm. 55. DOI: 10.1145/1379759.1379762  0.39
2008 Dobzinski S, Mehta A, Roughgarden T, Sundararajan M. Is shapley cost sharing optimal? Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4997: 327-336. DOI: 10.1016/J.Geb.2017.03.008  0.65
2008 Chen HL, Roughgarden T, Valiant G. Designing networks with good equilibria Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 854-863.  0.463
2007 Gupta A, Kumar A, Pál M, Roughgarden T. Approximation via cost sharing: Simpler and better approximation algorithms for network design Journal of the Acm. 54. DOI: 10.1145/1236457.1236458  0.501
2007 Buttyan L, Hubaux JP, Li LI, Li XY, Roughgarden T. Guest editorial non-cooperative behavior in networking Ieee Journal On Selected Areas in Communications. 25: 1065-1068. DOI: 10.1109/Jsac.2007.070801  0.386
2007 Roughgarden T. Routing games Algorithmic Game Theory. 461-486. DOI: 10.1017/CBO9780511800481.020  0.374
2007 Roughgarden T, Tardos É. Introduction to the inefficiency of equilibria Algorithmic Game Theory. 443-460. DOI: 10.1017/CBO9780511800481.019  0.387
2007 Haviv M, Roughgarden T. The price of anarchy in an exponential multi-server Operations Research Letters. 35: 421-426. DOI: 10.1016/J.Orl.2006.09.005  0.369
2007 Roughgarden T, Sundararajan M. Optimal efficiency guarantees for network design mechanisms Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4513: 469-483.  0.597
2006 Saha M, Roughgarden T, Latombe JC, Sánchez-Ante G. Planning tours of robotic arms among partitioned goals International Journal of Robotics Research. 25: 207-223. DOI: 10.1177/0278364906061705  0.315
2006 Cole R, Dodis Y, Roughgarden T. How much can taxes help selfish routing? Journal of Computer and System Sciences. 72: 444-467. DOI: 10.1016/J.Jcss.2005.09.010  0.531
2006 Roughgarden T. On the severity of Braess's Paradox: Designing networks for selfish users is hard Journal of Computer and System Sciences. 72: 922-953. DOI: 10.1016/J.Jcss.2005.05.009  0.478
2006 Chawla S, Roughgarden T, Sundararajan M. Optimal cost-sharing mechanisms for steiner forest problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4286: 112-123. DOI: 10.1007/11944874_11  0.614
2006 Roughgarden T. Potential functions and the inefficiency of equilibria International Congress of Mathematicians, Icm 2006. 3: 1071-1094.  0.342
2006 Chawla S, Roughgarden T. Single-source stochastic routing Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4110: 82-94.  0.306
2006 Roughgarden T, Sundararajan M. New trade-offs in cost-sharing mechanisms Proceedings of the Annual Acm Symposium On Theory of Computing. 2006: 79-88.  0.598
2005 Roughgarden T. Selfish routing with atomic players Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1184-1185.  0.319
2005 Lin H, Roughgarden T, Tardos E, Walkover A. Braess's Paradox, Fibonacci numbers, and exponential inapproximability Lecture Notes in Computer Science. 3580: 497-512.  0.367
2004 Roughgarden T. Stackelberg scheduling strategies Siam Journal On Computing. 33: 332-350. DOI: 10.1137/S0097539701397059  0.335
2004 Anshelevich E, Dasgupta A, Kleinberg J, Tardos E, Wexler T, Roughgarden T. The price of stability for network design with fair cost allocation Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 295-304. DOI: 10.1137/070680096  0.715
2004 Roughgarden T, Tardos É. Bounding the inefficiency of equilibria in nonatomic congestion games Games and Economic Behavior. 47: 389-403. DOI: 10.1016/J.Geb.2003.06.004  0.674
2004 Chudak FA, Roughgarden T, Williamson DP. Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation Mathematical Programming. 100: 411-421. DOI: 10.1007/S10107-003-0479-2  0.321
2004 Roughgarden T. The Maximum Latency of Selfish Routing Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 15: 973-974.  0.326
2003 Roughgarden T. The price of anarchy is independent of the network topology Journal of Computer and System Sciences. 67: 341-364. DOI: 10.1016/S0022-0000(03)00044-8  0.393
2003 Cole R, Dodis Y, Roughgarden T. Pricing network edges for heterogeneous selfish users Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 521-530.  0.423
2002 Roughgarden T, Tardos E. How bad is selfish routing? Journal of the Acm. 49: 236-259. DOI: 10.1145/506147.506153  0.701
2002 Kumar A, Gupta A, Roughgarden T. A constant-factor approximation algorithm for the multicommodity rent-or-buy problem Annual Symposium On Foundations of Computer Science - Proceedings. 333-342.  0.385
2001 Roughgarden T. Designing networks for selfish users is hard Annual Symposium On Foundations of Computer Science - Proceedings. 472-481.  0.323
Show low-probability matches.