David Gamarnik

Associate 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

Research Interests

applied probability, stochastic processes and queueing theory

applications to business processes and health care

random structures algorithms, random graphs

combinatorial optimization

Education

Ph.D. in Operations Research, MIT, 1998.
B.A. in Mathematics, Courant Institute of Math. Sci., NYU, 1993.

Awards

CV

Teaching

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.

Professional Activities

Publications: for most up to date publications see the http://arxiv.org

Recent talks:

Algorithmic challenges in the theory of queueing networks, Tutorial notes for Young European Queueing Theorists conference (YEQT V).
Statistical Physics, Interpolation Methods and Scaling Limits in Sparse Random Graphs, Microsoft Theory Colloquim.

Submitted

Stability of Skorokhod Problem is undecidable, with D. Katz.
On the Rate of Convergence to Stationarity of the M/M/N Queue in the Halfin-Whitt Regime, with D. Goldberg.
Performance analysis of queueing networks via robust optimization, with D. Bertsimas and A. Rikun.
Correlation decay and deterministic FPTAS for counting list-colorings of a graph, with D.Katz. Conference version in SODA07.

To appear

Belief Propagation for Min-cost Network Flow: Convergence & Correctness, with D. Shah and Y. Wei. Operations Research. Conference version in Proceedings of 21-st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
Counting independent sets using the Bethe approximation, with V. Chandrasekaran, M. Chertkov, D. Shah, and J. Shin, SIAM Journal On Discrete Mathematics, Under revision, 2009.

Appeared

Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, with M. Bayati and P. Tetali, Proceedings of STOC10.
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.
On deciding stability of queueing networks under priority scheduling policy, with D. Katz Annals of Applied Probability, Vol, 19, pp. 2008-2037, 2009.
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
First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction. 2^nd international Workshop on Internet & Network Economics, 2006.
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.