
Amin Saberi
Professor of Management Science and Engineering
Bio
Amin Saberi is an Associate Professor and 3COM faculty scholar in Stanford University. He received his B.Sc. from Sharif University of Technology and his Ph.D. from Georgia Institute of Technology in Computer Science. His research interests include algorithms, approximation algorithms, and algorithmic aspects of games, markets, and networks. Amin Saberi's research is supported by National Science Foundation (under grants CCF 0546889, 0729586, and 0915145), Library of Congress, Stanford Clean Slate Design for the Internet, and Google. His most recent awards include an Alfred Sloan Fellowship and best paper awards in FOCS 2011 and SODA 2010.
Professional Education
-
BS, Sharif Institute of Technology, Tehran, Iran, Computer Science (2000)
-
PhD, Georgia Institute of Technology, Computer Science (2004)
2020-21 Courses
- Approximation Algorithms
MS&E 319 (Win) - Mathematical Programming and Combinatorial Optimization
MS&E 112, MS&E 212 (Aut) - Network Structure and Epidemics
MS&E 235, MS&E 337 (Aut) -
Independent Studies (6)
- Advanced Reading and Research
CS 499 (Aut, Win, Spr) - Advanced Reading and Research
CS 499P (Aut, Win, Spr) - Directed Reading and Research
MS&E 408 (Aut, Win, Spr, Sum) - Part-time Curricular Practical Training
CS 390D (Aut, Win) - Ph.D. Research
CME 400 (Aut, Win, Spr) - Writing Intensive Senior Project (WIM)
CS 191W (Aut)
- Advanced Reading and Research
-
Prior Year Courses
2019-20 Courses
- Incentives and Algorithms
MS&E 230 (Spr) - Matching Theory
MS&E 319 (Aut) - Part-Time Practical Training
MS&E 208E (Aut) - Practical Training
MS&E 208A (Aut) - Practical Training
MS&E 208B (Aut) - Practical Training
MS&E 208C (Aut) - Practical Training
MS&E 208D (Aut)
2018-19 Courses
- Introduction to Optimization (Accelerated)
ENGR 62X, MS&E 111X, MS&E 211X (Win) - Matching Theory
MS&E 319 (Spr) - Mathematical Programming and Combinatorial Optimization
MS&E 112, MS&E 212 (Win)
2017-18 Courses
- Introduction to Optimization (Accelerated)
ENGR 62X, MS&E 111X, MS&E 211X (Win) - Network Analytics
MS&E 235 (Win)
- Incentives and Algorithms
Stanford Advisees
-
Postdoctoral Faculty Sponsor
David Wajc -
Doctoral Dissertation Advisor (AC)
Kristen Kessel -
Master's Program Advisor
Sarah Egler, Jackson Eilers, Marissa Gerchick, Aiden Ho, Daniel Jun, Raymond Lee, Vibha Puri, Hope Schroeder, Jaymee Sheng -
Doctoral (Program)
Yeganeh Ali Mohammadi, Tristan Pollner, Mohammad Roghani
All Publications
-
Message-Passing Algorithms for Sparse Network Alignment
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
2013; 7 (1)
View details for DOI 10.1145/2435209.2435212
View details for Web of Science ID 000316415700003
-
Dynamic Pay-Per-Action Mechanisms and Applications to Online Advertising
OPERATIONS RESEARCH
2013; 61 (1): 98-111
View details for DOI 10.1287/opre.1120.1124
View details for Web of Science ID 000316115000008
-
Algorithmic Solutions for Envy-Free Cake Cutting
OPERATIONS RESEARCH
2012; 60 (6): 1461-1476
View details for DOI 10.1287/opre.1120.1116
View details for Web of Science ID 000312468800012
-
Online Stochastic Matching: Online Actions Based on Offline Statistics
MATHEMATICS OF OPERATIONS RESEARCH
2012; 37 (4): 559-573
View details for DOI 10.1287/moor.1120.0551
View details for Web of Science ID 000314284200001
-
Santa Claus Meets Hypergraph Matchings
ACM TRANSACTIONS ON ALGORITHMS
2012; 8 (3)
View details for DOI 10.1145/2229163.2229168
View details for Web of Science ID 000307170500005
-
Online Optimization with Uncertain Information
ACM TRANSACTIONS ON ALGORITHMS
2012; 8 (1)
View details for DOI 10.1145/2071379.2071381
View details for Web of Science ID 000301391300002
-
Distributed Node Placement Algorithms for Constructing Well-Connected Sensor Networks
IEEE INFOCOM Conference
IEEE. 2012: 810–818
View details for Web of Science ID 000309279500091
-
Price of Correlations in Stochastic Optimization
OPERATIONS RESEARCH
2012; 60 (1): 150-162
View details for DOI 10.1287/opre.1110.1011
View details for Web of Science ID 000302113900013
-
Discrete Fixed Points: Models, Complexities, and Applications
MATHEMATICS OF OPERATIONS RESEARCH
2011; 36 (4): 636-652
View details for DOI 10.1287/moor.1110.0511
View details for Web of Science ID 000296977700004
-
Some computational tools for digital archive and metadata maintenance
BIT NUMERICAL MATHEMATICS
2011; 51 (1): 127-154
View details for DOI 10.1007/s10543-011-0324-6
View details for Web of Science ID 000288707100007
-
A Randomized Rounding Approach to the Traveling Salesman Problem
52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)
IEEE COMPUTER SOC. 2011: 550–559
View details for DOI 10.1109/FOCS.2011.80
View details for Web of Science ID 000298962700059
-
Online Stochastic Matching: Online Actions Based on Offline Statistics
22nd Annual ACM/SIAM Symposium on Discrete Algorithms
SIAM. 2011: 1285–1294
View details for Web of Science ID 000296182400098
-
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus
22nd Annual ACM/SIAM Symposium on Discrete Algorithms
SIAM. 2011: 967–975
View details for Web of Science ID 000296182400075
-
A Sequential Algorithm for Generating Random Graphs
ALGORITHMICA
2010; 58 (4): 860-910
View details for DOI 10.1007/s00453-009-9340-1
View details for Web of Science ID 000282089900003
-
The spread of innovations in social networks
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
2010; 107 (47): 20196-20201
Abstract
Which network structures favor the rapid spread of new ideas, behaviors, or technologies? This question has been studied extensively using epidemic models. Here we consider a complementary point of view and consider scenarios where the individuals' behavior is the result of a strategic choice among competing alternatives. In particular, we study models that are based on the dynamics of coordination games. Classical results in game theory studying this model provide a simple condition for a new action or innovation to become widespread in the network. The present paper characterizes the rate of convergence as a function of the structure of the interaction network. The resulting predictions differ strongly from the ones provided by epidemic models. In particular, it appears that innovation spreads much more slowly on well-connected network structures dominated by long-range links than in low-dimensional ones dominated, for example, by geographic proximity.
View details for DOI 10.1073/pnas.1004098107
View details for Web of Science ID 000284529000013
View details for PubMedID 21076030
View details for PubMedCentralID PMC2996710
-
Advertisement allocation for generalized second-pricing schemes
OPERATIONS RESEARCH LETTERS
2010; 38 (6): 571-576
View details for DOI 10.1016/j.orl.2010.09.002
View details for Web of Science ID 000284496700018
-
How to Distribute Antidote to Control Epidemics
RANDOM STRUCTURES & ALGORITHMS
2010; 37 (2): 204-222
View details for DOI 10.1002/rsa.20315
View details for Web of Science ID 000281045300003
-
On the Dynamic Response of a Saturating Static Feedback-Controlled Single Integrator Driven by White Noise
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
2010; 55 (4): 959-965
View details for DOI 10.1109/TAC.2010.2041608
View details for Web of Science ID 000276251300014
-
Approximating power indices: theoretical and empirical analysis
AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS
2010; 20 (2): 105-122
View details for DOI 10.1007/s10458-009-9078-9
View details for Web of Science ID 000273978500001
-
An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem
21st Annual ACM/SIAM Symposium on Discrete Algorithms
SIAM. 2010: 379–389
View details for Web of Science ID 000280699900032
-
Correlation Robust Stochastic Optimization
21st Annual ACM/SIAM Symposium on Discrete Algorithms
SIAM. 2010: 1087–1096
View details for Web of Science ID 000280699900088
-
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
42nd ACM Symposium on Theory of Computing
ASSOC COMPUTING MACHINERY. 2010: 57–65
View details for Web of Science ID 000286949900006
-
AN APPROXIMATION ALGORITHM FOR MAX-MIN FAIR ALLOCATION OF INDIVISIBLE GOODS
SIAM JOURNAL ON COMPUTING
2010; 39 (7): 2970-2989
View details for DOI 10.1137/080723491
View details for Web of Science ID 000280847900010
-
Cutting a Cake for Five People
5th International Conference on Algorithmic Aspects in Information and Management
SPRINGER-VERLAG BERLIN. 2009: 292–300
View details for Web of Science ID 000268031100023
-
Algorithms for Large, Sparse Network Alignment Problems
9th IEEE International Conference on Data Mining
IEEE. 2009: 705–710
View details for Web of Science ID 000287216600074
-
Convergence to Equilibrium in Local Interaction Games
50th Annual IEEE Symposium on Foundations of Computer Science
IEEE COMPUTER SOC. 2009: 303–312
View details for DOI 10.1109/FOCS.2009.64
View details for Web of Science ID 000278330300030
-
Generating random Tanner-graphs with large girth
IEEE Information Theory Workshop (ITW)
IEEE. 2009: 154–157
View details for Web of Science ID 000305809200032
-
Generating Random Graphs with Large Girth
20th Annual ACM-SIAM Symposium on Discrete Algorithms
SIAM. 2009: 566–575
View details for Web of Science ID 000281447000063
-
On the Inefficiency Ratio of Stable Equilibria in Congestion Games
5th International Workshop on Internet and Network Economics
SPRINGER-VERLAG BERLIN. 2009: 545–552
View details for Web of Science ID 000278097500054
-
The complexity of equilibria: Hardness results for economies via a correspondence with games
Workshop on Excursions in Algoritmics
ELSEVIER SCIENCE BV. 2008: 188–98
View details for DOI 10.1016/j.tcs.2008.08.007
View details for Web of Science ID 000261416700010
-
Market Equilibrium via a Primal-Dual Algorithm for a Convex Program
JOURNAL OF THE ACM
2008; 55 (5)
View details for DOI 10.1145/1411509.1411512
View details for Web of Science ID 000260916000003
-
On the disturbance response and external stability of a saturating static-feedback-controlled double integrator
AUTOMATICA
2008; 44 (8): 2191-2196
View details for DOI 10.1016/j.automatica.2007.11.005
View details for Web of Science ID 000258963700031
-
A Monte Carlo method for solving unsteady adjoint equations
JOURNAL OF COMPUTATIONAL PHYSICS
2008; 227 (12): 6184-6205
View details for DOI 10.1016/j.jcp.2008.03.006
View details for Web of Science ID 000256502100012
-
Minimizing effective resistance of a graph
SIAM REVIEW
2008; 50 (1): 37-66
View details for DOI 10.1137/050645452
View details for Web of Science ID 000253646600004
-
Stochastic Submodular Maximization
4th International Workshop on Internet and Network Economics
SPRINGER-VERLAG BERLIN. 2008: 477–489
View details for Web of Science ID 000262046200044
-
A Fast and Simple Algorithm for Computing Market Equilibria
4th International Workshop on Internet and Network Economics
SPRINGER-VERLAG BERLIN. 2008: 19–30
View details for Web of Science ID 000262046200002
-
Santa Claus Meets Hypergraph Matchings
11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/12th International Workshop on Randomization and Computation
SPRINGER-VERLAG BERLIN. 2008: 10–20
View details for Web of Science ID 000260573700002
-
Cell breathing in wireless LANs: Algorithms and evaluation
IEEE TRANSACTIONS ON MOBILE COMPUTING
2007; 6 (2): 164-178
View details for Web of Science ID 000242856000003
-
AdWords and generalized Online matching
JOURNAL OF THE ACM
2007; 54 (5)
View details for DOI 10.1145/1284320.1284321
View details for Web of Science ID 000250557900001
-
An Approximation Alaorithm for Max-Min Fair Allocation of Indivisible Goods
39th Annual ACM Symposium on Theory of Computing
ASSOC COMPUTING MACHINERY. 2007: 114–121
View details for Web of Science ID 000267050000013
-
A sequential algorithm for generating random graphs
10th Int Workshop on Approximation Algorithms for Combinatorial Optimization Problems/11th Int Workshop on Randomization and Computation
SPRINGER-VERLAG BERLIN. 2007: 326–340
View details for Web of Science ID 000250357100024
-
Allocating Online Advertisement Space with Unreliable Estimates
8th Annual Conference on Electronic Commerce (EC 2007)
ASSOC COMPUTING MACHINERY. 2007: 288–294
View details for Web of Science ID 000268330200034
-
Towards topology aware networks
26th IEEE Conference on Computer Communications (INFOCOM 2007)
IEEE. 2007: 2591–2595
View details for Web of Science ID 000249117704087
-
Approximating Nash Equilibria using Small-Support Strategies
8th Annual Conference on Electronic Commerce (EC 2007)
ASSOC COMPUTING MACHINERY. 2007: 352–354
View details for Web of Science ID 000268330200041
-
On certain connectivity properties of the Internet topology
44th Annual IEEE Symposium on Foundations of Computer Science
ACADEMIC PRESS INC ELSEVIER SCIENCE. 2006: 239–51
View details for DOI 10.1016/j.jcss.2005.06.009
View details for Web of Science ID 000236042100004
-
A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks
47th Annual IEEE Symposium on Foundations of Computer Science
IEEE COMPUTER SOC. 2006: 69–76
View details for Web of Science ID 000242526200007
-
Leontief Economies Encode Nonzero Sum Two-Player Games
17th ACM-SIAM Symposium on Discrete Algorithms
SIAM. 2006: 659–667
View details for Web of Science ID 000281596300072
-
Hybrid search schemes for unstructured peer-to-peer networks
24th Annual Joint Conference of the IEEE Computer and Communications Societies
IEEE COMPUTER SOC. 2005: 1526–1537
View details for Web of Science ID 000231441002003
-
Price of anarchy, locality gap, and a network service provider game
1st International Workshop on Internet and Network Economics
SPRINGER-VERLAG BERLIN. 2005: 1046–1055
View details for Web of Science ID 000234851600105
-
On the hardness of optimal auctions
43rd Annual IEEE Symposium on Foundations of Computer Science
IEEE COMPUTER SOC. 2002: 396–405
View details for Web of Science ID 000179945300040