Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
David Gamarnik
2010 – today
- 2013
[i7]David Gamarnik, Madhu Sudan: Limits of local algorithms over sparse random graphs. CoRR abs/1304.1831 (2013)- [i6]David Gamarnik, Madhu Sudan: Limits of local algorithms over sparse random graphs. Electronic Colloquium on Computational Complexity (ECCC) 20: 55 (2013)
- 2012
- [j32]David Gamarnik, Devavrat Shah, Yehua Wei: Belief Propagation for Min-Cost Network Flow: Convergence and Correctness. Operations Research 60(2): 410-428 (2012)
- [j31]David Gamarnik, Dmitriy Katz: Correlation decay and deterministic FPTAS for counting colorings of a graph. J. Discrete Algorithms 12: 29-47 (2012)
- [j30]David Gamarnik, Alexander L. Stolyar: Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution. Queueing Syst. 71(1-2): 25-51 (2012)
- [i5]David Gamarnik, Dmitriy Katz, Sidhant Misra: Strong spatial mixing for list coloring of graphs. CoRR abs/1207.1223 (2012)
- 2011
- [j29]Dimitris Bertsimas, David Gamarnik, Alexander Anatoliy Rikun: Performance Analysis of Queueing Networks via Robust Optimization. Operations Research 59(2): 455-466 (2011)
- [j28]Abraham Flaxman, David Gamarnik, Gregory B. Sorkin: First-passage percolation on a ladder graph, and the path cost in a VCG auction. Random Struct. Algorithms 38(3): 350-364 (2011)
- [j27]Venkat Chandrasekaran, Misha Chertkov, David Gamarnik, Devavrat Shah, Jinwoo Shin: Counting Independent Sets Using the Bethe Approximation. SIAM J. Discrete Math. 25(2): 1012-1034 (2011)
- 2010
- [j26]David Gamarnik, David A. Goldberg: Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections. Combinatorics, Probability & Computing 19(1): 61-85 (2010)
- [j25]David Gamarnik, Dmitriy Katz: A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix. J. Comput. Syst. Sci. 76(8): 879-883 (2010)
- [j24]David Gamarnik, Sean P. Meyn: On exponential ergodicity of multiclass queueing networks. Queueing Syst. 65(2): 109-133 (2010)
- [c21]David Gamarnik, David Goldberg, Theophane Weber: PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs. SODA 2010: 268-278
- [c20]David Gamarnik, Devavrat Shah, Yehua Wei: Belief Propagation for Min-cost Network Flow: Convergence & Correctness. SODA 2010: 279-292
- [c19]Mohsen Bayati, David Gamarnik, Prasad Tetali: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. STOC 2010: 105-114
- [i4]David Gamarnik, Devavrat Shah, Yehua Wei: Belief Propagation for Min-cost Network Flow: Convergence and Correctness. CoRR abs/1004.1586 (2010)
- [i3]David Gamarnik, Dmitriy Katz: Stability of Skorokhod problem is undecidable. CoRR abs/1007.1694 (2010)
2000 – 2009
- 2009
- [c18]David Gamarnik, Dmitriy Katz: Sequential cavity method for computing limits of the log-partition function for lattice models. SODA 2009: 596-605
- [i2]David Gamarnik, David Goldberg, Theophane Weber: Correlation Decay in Random Decision Networks. CoRR abs/0912.0338 (2009)
- 2008
- [j23]Antar Bandyopadhyay, David Gamarnik: Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models. Random Struct. Algorithms 33(4): 452-479 (2008)
- [i1]David Gamarnik, David A. Goldberg: Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections. CoRR abs/0807.1277 (2008)
- 2007
- [j22]David Gamarnik: On the Undecidability of Computing Stationary Distributions and Large Deviation Rates for Constrained Random Walks. Math. Oper. Res. 32(2): 257-265 (2007)
- [c17]David Gamarnik, Dmitriy Katz: Correlation decay and deterministic FPTAS for counting list-colorings of a graph. SODA 2007: 1245-1254
- [c16]Mohsen Bayati, David Gamarnik, Dimitriy A. Katz, Chandra Nair, Prasad Tetali: Simple deterministic approximation algorithms for counting matchings. STOC 2007: 122-127
- 2006
- [j21]
- [j20]David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz: Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method. Random Struct. Algorithms 28(1): 76-106 (2006)
- [c15]Antar Bandyopadhyay, David Gamarnik: Counting without sampling: new algorithms for enumeration problems using statistical physics. SODA 2006: 890-899
- [c14]Abraham Flaxman, David Gamarnik, Gregory B. Sorkin: First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction. WINE 2006: 99-111
- 2005
- [j19]David Gamarnik, Maxim Sviridenko: Hamiltonian completions of sparse random graphs. Discrete Applied Mathematics 152(1-3): 139-158 (2005)
- [j18]David Gamarnik, Moshe Lewenstein, Maxim Sviridenko: An improved upper bound for the TSP in cubic 3-edge-connected graphs. Oper. Res. Lett. 33(5): 467-474 (2005)
- [j17]Abraham D. Flaxman, David Gamarnik, Gregory B. Sorkin: Embracing the giant component. Random Struct. Algorithms 27(3): 277-289 (2005)
- [c13]David Gamarnik: The expected value of random minimal length spanning tree of a complete graph. SODA 2005: 700-704
- 2004
- [j16]Béla Bollobás, David Gamarnik, Oliver Riordan, Benny Sudakov: On the Value of a Random Minimum Weight Steiner Tree. Combinatorica 24(2): 187-207 (2004)
- [j15]David Gamarnik: Stochastic Bandwidth Packing Process: Stability Conditions via Lyapunov Function Technique. Queueing Syst. 48(3-4): 339-363 (2004)
- [j14]Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin: Random MAX SAT, random MAX CUT, and their phase transitions. Random Struct. Algorithms 24(4): 502-545 (2004)
- [j13]David Gamarnik, Petar Momcilovic: An asymptotic optimality of the transposition rule for linear lists. SIGMETRICS Performance Evaluation Review 32(2): 33-34 (2004)
- [c12]David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz: Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results Using the Local Weak Convergence Method. APPROX-RANDOM 2004: 357-368
- [c11]Abraham Flaxman, David Gamarnik, Gregory B. Sorkin: Embracing the Giant Component. LATIN 2004: 69-79
- [c10]David Gamarnik: Linear phase transition in random linear constraint satisfaction problems. SODA 2004: 111-120
- 2003
- [j12]Dimitris Bertsimas, David Gamarnik, Jay Sethuraman: From Fluid Relaxations to Practical Algorithms for High-Multiplicity Job-Shop Scheduling: The Holding Cost Objective. Operations Research 51(5): 798-813 (2003)
- [j11]David Gamarnik: Stability of Adaptive and Nonadaptive Packet Routing Policies in Adversarial Queueing Networks. SIAM J. Comput. 32(2): 371-385 (2003)
- [j10]David Gamarnik, John J. Hasenbein: Weak instability in stochastic and fluid queueing networks. SIGMETRICS Performance Evaluation Review 31(2): 9-10 (2003)
- [j9]David Gamarnik: Extension of the PAC framework to finite and countable Markov chains. IEEE Transactions on Information Theory 49(1): 338-345 (2003)
- [c9]David Gamarnik: Linear Phase Transition in Random Linear Constraint Satisfaction Problems. DRW 2003: 113-126
- [c8]Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin: Random MAX SAT, random MAX CUT, and their phase transitions. SODA 2003: 364-373
- 2002
- [j8]David Gamarnik: On Deciding Stability of Constrained Homogeneous Random Walks and Queueing Systems. Math. Oper. Res. 27(2): 272-293 (2002)
- [j7]Don Coppersmith, David Gamarnik, Maxim Sviridenko: The diameter of a long-range percolation graph. Random Struct. Algorithms 21(1): 1-13 (2002)
- [j6]David Gamarnik: Computing stationary probability distributions and large deviation rates for constrained random walks.: the undecidability results. SIGMETRICS Performance Evaluation Review 30(3): 38-40 (2002)
- [c7]Don Coppersmith, David Gamarnik, Maxim Sviridenko: The diameter of a long range percolation graph. SODA 2002: 329-337
- 2001
- [j5]David Gamarnik: On deciding stability of constrained random walks and queueing systems. SIGMETRICS Performance Evaluation Review 28(4): 39-40 (2001)
- [j4]David Gamarnik: Stochastic online binpacking problem: exact conditions for bounded expected queue lengths under the best fit packing heuristic. SIGMETRICS Performance Evaluation Review 29(3): 30-31 (2001)
- 2000
- [c6]David Gamarnik: On deciding stability of scheduling policies in queueing systems. SODA 2000: 467-476
1990 – 1999
- 1999
- [j3]Dimitris Bertsimas, David Gamarnik: Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet Routing. J. Algorithms 33(2): 296-318 (1999)
- [j2]Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis: Estimation of Time-Varying Parameters in Statistical Models: An Optimization Approach. Machine Learning 35(3): 225-245 (1999)
- [j1]Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis: Performance analysis of multiclass queueing networks. SIGMETRICS Performance Evaluation Review 27(3): 11-14 (1999)
- [c5]David Gamarnik: Extension of the PAC Framework to Finite and Countable Markov Chains. COLT 1999: 308-317
- [c4]David Gamarnik: Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks. STOC 1999: 206-214
- 1998
- [c3]David Gamarnik: Efficient Learning of Monotone Concepts via Quadratic Optimization. COLT 1998: 134-143
- [c2]
- 1997
- [c1]Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis: Estimation of Time-Varying Parameters in Statistical Models: An Optimization Approach. COLT 1997: 314-324
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-05-03 21:45 CEST by the dblp team