|
|
|
David Gamarnik
Professor of Operations Research MIT Sloan School of Management, E62-563 100 Main Street Cambridge, MA 02139 Email: last
name at mit dot edu Tel: 617-253-7779 Fax:617-258-7579 |
|
|
My webpage is truly out of
date and obsolete. It will be redesigned and reposted soon!..
For most recent pubs see
https://scholar.google.com/citations?user=qMDr8HUAAAAJ&hl=en
and
https://arxiv.org/search/?searchtype=author&query=Gamarnik%2C+D
Research Interests
Applied
probability, stochastic processes and queueing theory
Random
structures and random graphs
Combinatorial
optimization
Statistical
learning theory
Applications
to business processes and health care
Education
- Ph.D. in Operations Research, MIT, 1998.
- B.A. in Mathematics, Courant Institute of Math.
Sci., NYU, 1993.
Awards
CV
Teaching
- 6.268 Network Science
and Models.
- 15.060 Data Models and Decisions.
- 6.436/15.085
Fundamentals of Probability.
- 15.066J System Optimization and Analysis
- 15.072
Queues: Theory and Applications.
- 15.070 Advanced Stochastic Processes.
- 6.979/15.098 Applied Probability Seminar.
Professional Activities
Publications:
for most up to date publications
see the http://arxiv.org/find/all/1/all:+gamarnik/0/1/0/all/0/1
Recent talks
Tutorials
and Survey Articles
·
Correlation
Decay Method for Decision, Optimization and Inference
in Large Scale Networks, TutORials in Operations
Research, INFORMS, 2013.
·
Fluid
Models of Queueing Networks, Wiley
Encyclopedia of Operations Research and Management Science, 2010.
Submitted
- Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem, with M. Sudan.
- Convergent sequences of sparse graphs: A large deviations approach, with C. Borgs and J. Chayes.
- Giant Component in Random Multipartite Graphs with Given Degree Sequences, with S. Misra.
- Stability of Skorokhod Problem is undecidable, with D. Katz.
- Scheduling interns at hospitals: Queueing models and fluid approximations, with R. Anderson.
To appear
- Right-convergence
of sparse random graphs. Probability Theory and Related Fields.
- Strong spatial mixing for list coloring of graphs, with D. Katz and
S. Misra. Random
Structures and Algorithms.
- Correlation Decay in Random Decision Networks, with D. Goldberg and T. Weber. Mathematics of Operations Research.
Appeared
- Limits of local algorithms over sparse random graphs, with M. Sudan.
Proceedings of the 5-th Innovations in Theoretical Computer Science
conference, 2014.
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, with M. Bayati and P. Tetali. Annals of Probability, Vol. 41, pp. 4080-4115, 2013. Conference version in Proceedings of STOC10.
- Steady-state GI/GI/n queue in the Halfin-Whitt regime, with D. Goldberg. Annals of Applied Probability, Vol. 23, pp. 2382-2419, 2013.
- On the Rate of Convergence to Stationarity of the M/M/N Queue in the Halfin-Whitt Regime, with D. Goldberg. Annals of Applied Probability, Vol. 23, pp. 1879-1912, 2013.
- Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime. Asymptotics of the stationary distribution, with A. Stolyar. Queueing Systems, Vol. 71, pp 25-51, 2012.
- Counting independent sets using the Bethe approximation, with V. Chandrasekaran, M. Chertkov, D. Shah, and J. Shin, SIAM Journal On Discrete Mathematics, Vol. 25, pp. 1012-1034, 2011.
- The need for (long) chains
in kidney exchange, with I. Ashlagi and A.
Roth. National Bureau of Economic
Research. Market Design Working Group Meeting, 2011.
- Belief Propagation for Min-cost Network Flow: Convergence & Correctness, with D. Shah and Y. Wei. Operations Research. Vol. 60, pp. 410-428, 2012. Conference version in Proceedings of 21-st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
- Correlation
decay and deterministic FPTAS for counting list-colorings of a graph,
with D.Katz.
Journal of Discrete Algorithms, Vol. 12. pp. 29–47, 2012. Conference
version in SODA07.
- First-passage percolation on a ladder graph, and the path cost in a
VCG auction, with A. Flaxman and G. Sorkin. Random
Structures and Algorithms, 38:350–364, 2011.
- Performance analysis of queueing networks via robust optimization, with D. Bertsimas and A. Rikun. Operations Research, 59:455–466, 2011.
- On exponential ergodicity of multiclass queueing networks, with S. Meyn. Queueing Systems, Vol. 65. pp. 109-133, 2010.
- Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections, with D. Goldberg, Combinatorics, Probability and Computing, Vol 19, pp 61-85, 2010
- On deciding stability of multiclass queueing networks under buffer priority scheduling policies, with D. Katz, Annals of Applied Probability, Vol. 19, pp 2008-2037, 2009.
- Sequential cavity method and applications to free energy computations, with D. Katz. Journal of Statistical Physics (2009) 137: 205–232. Conference version in SODA09.
- Simple deterministic approximation algorithms for counting matchings, with M. Bayati, D. Katz, C. Nair and P. Tetali. Proceedings of STOC 2007.
- Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix, with D. Katz. Journal of Computer and System Sciences, Vol. 76 (2010) 879–883.
- PTAS for maximum weight independent set problem with random weights in bounded degree graphs, with D. Goldberg and T.Weber . In Proceedings of 21-st ACM-SIAM Symposium on Discrete Algorithms, (SODA), 2010.
- Counting without sampling. New algorithms for enumeration problems using statistical physics, with Antar Bandyopadhyay. Random Structures and Algorithms, 33(4), 2008. Preliminary version in SODA2006.
- Invariant probability measures and dynamics of exponential linear type maps, with T. Nowicki, and G. Swirszcz. Ergodic Theory and Dynamical Systems, 28(1):1479-1495, 2008.
- A Model for Understanding the Impacts of Demand & Capacity on Waitlists in a Congested Recovery Room, with T. Schoenmeyr, P. Dunn, B. Daily, D. Berger, W. Levine, and W. Sandberg. Anesthesiology 2 110:1293–304, 2009.
- Steady-state analysis of a multi-server queue in the Halfin-Whitt regime, with P. Momcilovic. Advances in Applied Probability, 40:548–577, 2008.
- Computing Stationary Probability Distribution and Large Deviations Rates for Constrained Homogeneous Random Walks. The Undecidability Results. Mathematics of Operations Research, Vol. 32, No. 2, pp. 257-265, 2007.
- Modeling operational risks in business processes, with Feng Cheng, Nitin Jengte, Wanli Min, Bala Ramachandran. The Journal of Operational Risk. Vol.2, No. 2, pp. 73-98, 2007
- Validity of Heavy Traffic Steady-State Approximations in Open Queueing Networks, with A. Zeevi. Annals of Applied Probability, Vol. 16 No. 1, pp.66-90, 2006.
- Handling Load With Less Stress, with N. Bansal. Queueing Systems, Volume 54, No1, pp. 45-54, 2006.
- Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method, with T. Nowicki and G. Swirscsz. Random Structures and Algorithm, Vol.28, No. 1, pp. 76-106. 2005.
- Hamiltonian Completion of Sparse Random Graphs, with M. Sviridenko. Discrete Applied Mathematics, Volume 152, pp.139-158, 2005.
- Asymptotic
Optimality of the Transposition Rule in Linear Lists, with P. Momcilovic. Journal of Applied Probability, 42(1): 235-246,
2005.
- Embracing the giant component, with A. Flaxman and G. Sorkin. Submitted. Random Structures and Algorithms, Vol.24, No. 4, pp.277 -289. 2005
- Instability in Stochastic and Fluid Queueing Networks, with J.Hasenbein. Annals of Applied Probability, Vol. 15. No. 3, 2005.
- Analysis of Stochastic Online Bin Packing Processes, with M. Squillante. Stochastic Models, Vol. 21. pp 401-425, 2005.
- Expectation of the random minimal length spanning tree of a complete graph. SODA05.
- An Improved Upper Bound for TSP in
Cubic 3-Connected Graphs, with M. Lewenstein
and M. Sviridenko.
Operations Research Letters, Vol. 33. pp. 467-474, 2005.
- Stochastic Online Bin Packing Problem: Exact Conditions for Stability under the Best Fit Heuristic. Queuing Systems, Vol. 48. pp. 339-363, 2004.
- On the Value of a Random Minimum Length Steiner Tree, with B. Bollobas, O. Riordan and B. Sudakov. Combinatorica. Vol 24, No.2, pp.187-207. 2004.
- Linear Phase Transition in Random Linear Constraint Satisfaction Problems. Probability Theory and the Related Fields, Vol. 129, No.3, pp.410-440 2004. Preliminary version appeared in SODA 2004
- Random MAX 2-SAT and MAX CUT, with D. Coppersmith, M. Hajiaghayi and G. Sorkin. Random Structures and Algorithms, Vol.24, No. 4, pp. 502-545. 2004. Preliminary version appeared in SODA 2003
- Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks, SIAM Journal on Computing, vol.32,No.2, pp. 371 – 385. 2003. Preliminary version appeared in Proc. 31st ACM Symposium on Theory of Computing, 1999.
- Extension of the PAC Framework to Finite and Countable Markov Chains, IEEE Transactions on Information Theory, vol. 49, No 1, pp. 338-345. 2003
- From Fluid Relaxations to Practical Algorithms for Job Shop Scheduling: the Holding Cost Objective, with D. Bertsimas and J. Sethuraman. Operations Research. Vol. 51, No 5, pp. 798-813, 2003.
- The Diameter of a Long-Range Percolation Graph, with D. Coppersmith and M. Sviridenko. Random Structures and Algorithms, vol.21, pp. 1-13, 2002.
- Performance of Multiclass Markovian Queueing Networks via Piecewise Linear Lyapunov Functions, with D. Bertsimas.and J. Tsitsiklis. Annals of Applied Probability. vol.11, No.4, pp.1384-1428, 2002.
- On Deciding Stability of Some Scheduling
Policies in Queueing Systems, Mathematics of Operations Research.
vol.27, No.2, pp.272-294, 2002. Preliminary version appeared in SODA2000.
- Static and Dynamic Hot-Potato Packet Routing in Communication Networks, with M. Sviridenko. IBM Technical Report # RC21918. 2000.
- Using Fluid Models to Prove Stability of Adversarial Queueing Networks, IEEE Trans. Automat. Control, vol.45, pp.741-746, 2000. Preliminary version appeared in 39th Symposium on Foundations of Computer Science, 1998.
- Asymptotically Optimal Algorithm for Job Shop Scheduling and Packet Routing, with D. Bertsimas. Journal of Algorithms, 33(2): pp.296-318, 1999.
- Estimation of Time-Varying Parameters in Statistical Models: An Optimization Approach,with D. Bertsimas and J. Tsitsiklis. Invited paper in a special issue of Machine Learning 35(3): pp.225-245, 1999.
- Stability and Performance of Multiclass Queueing Networks, MIT Thesis, 1998.
- Efficient Learning of Monotone Concepts via Quadratic Optimization, in Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998.
- Stability Conditions for Multiclass Fluid Queueing Networks, with D. Bertsimas and J. Tsitsiklis. IEEE Trans. Automat. Control, vol.41, pp.1618-1631, 1996
- Minimality of the Group AUT(C). SERDICA - Bulgaricae mathematicae publicationes, vol.17, pp.197-201, 1991.