David Gamarnik

Assistant Professor of Operations Research

MIT Sloan School of Management, E53-353

77 Massachusetts Avenue

Cambridge, MA 02139

Email: last name at mit dot edu

Tel: 617-253-7779

Fax:617-258-7579

Research Interests

stochastic processes and queueing theory

applications to business processes

probabilistic combinatorics

algorithms and combinatorial optimization

scheduling

statistical learning theory

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

Submitted

A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix, with D. Katz.
Sequential cavity method and applications to free energy computations, with D. Katz. Conference version in SODA09.
Simple deterministic approximation algorithms for counting matchings, with M. Bayati, D. Katz, C. Nair and P. Tetali. Conference version in STOC07.
Correlation decay and deterministic FPTAS for counting list-colorings of a graph, with D.Katz. Conference version in SODA07.
On Exponential Ergodicity of Multiclass Queueing Networks, with S. Meyn.
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.

To appear

On deciding stability of multiclass queueing networks under buffer priority scheduling policies, with D. Katz. Annals of Applied Probability.
Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections, with D. Goldberg. Accepted to Combinatorics, Probability and Computing.
Counting without sampling. New algorithms for enumeration problems using statistical physics, with Antar Bandyopadhyay. Random Structures and Algorithms. Preliminary version in SODA2006.

Appeared

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.
Counting without sampling. Asymptotics of the log-partition function for certain statistical physics models, with A. Bandyopadhyay. Random Structures and Algorithms, 33(4), 2008.
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.