153 citations · 157 across the 3 of their papers we have counts for
6 papers · 1 filter
Validity of heavy traffic steady-state approximations in generalized Jackson Networks
David Gamarnik, Assaf Zeevi
We consider a single class open queueing network, also known as a generalized Jackson network (GJN). A classical result in heavy-traffic theory asserts that the sequence of normali…
A Transposition Rule Analysis Based on a Particle Process
David Gamarnik, Petar Momcilovic
A linear list is a collection of items that can be accessed sequentially. The cost of a request is the number of items that need to be examined before the desired item is located,…
Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method
David Gamarnik, Tomasz Nowicki, Grzegorz Swirscsz
Let and be an -node sparse random graph and a sparse random -regular graph, respectively, and let and be the sizes of the…
Linear Phase Transition in Random Linear Constraint Satisfaction Problem
David Gamarnik
Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints C on K variables is fixed. From a pool of…
Computing stationary probability distributions and large deviation rates for constrained random walks. The undecidability results
David Gamarnik
Our model is a constrained homogeneous random walk in a nonnegative orthant Z_+^d. The convergence to stationarity for such a random walk can often be checked by constructing a Lya…
The diameter of a long range percolation graph
Don Coppersmith, David Gamarnik, Maxim Sviridenko
We consider the following long range percolation model: an undirected graph with the node set , has edges $(\x,\y)$ selected with probability $\approx β/||\x-\y||^…