The objective method: Probabilistic combinatorial optimization and local weak convergence
This survey describes a general approach to a class of problems that arise in combinatorial probability and combinatorial optimization. Formally, the method is part of weak convergence theory, but in concrete problems the method has a flavor of its own. A characteristic element of the method is that it often calls for one to introduce a new, infinite, probabilistic object whose local properties inform us about the limiting properties of a sequence of finite problems. Section 2 develops the notion of local weak convergence and introduces the ``standard construction, which is a general recipe for building rooted geometric graphs. The theory of the maximum partial matching problem is developed in Section 3. In Section 4 the authors introduce the mean-field model of distance which is a physically motivated probability model designed to gain isight into problems for point processes. The mean-field model leads us to the PWIT, or Poisson weighted infinite tree, which is arguably the most important infinite tree model. The relationship of the PWIT to problems of combinatorial optimization is continued is Section 5. The probability theory of Euclidean combinatorial optimization is presented in Section 6. In Section 7, the last section, the authors summarize some of the circumstances that seem to be needed for the objective method to be successful and develop the background of an attractive conjecture on the independence number of a random regular graph. This survey also contains new results. In particular, the material in Section 3 on the maximum partial matching problem is new, including the basic limit theorem (Theorem 3.3) and the theorem that determines the limit constants (Theorem 3.4). Another new result is the convergence theorem for minimal spanning trees (Theorem 5.4). For the entire collection see [Zbl 1025.60001].
- scientific article; zbMATH DE number 1839489
- Maximum Weight Partial Colorings on Sparse Random Graphs
- Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
- The scaling limits of the minimal spanning tree and invasion percolation in the plane
- Local neighbourhoods for first-passage percolation on the configuration model
- Load balancing in hypergraphs
- Limiting properties of random graph models with vertex and edge weights
- First steps in combinatorial optimization on graphons: matchings
- Heavy subtrees of Galton-Watson trees with an application to Apollonian networks
- Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
- A framework for imperfectly observed networks
- Gaussian limits for random measures in geometric probability
- Scaling limits for width two partially ordered sets: the incomparability window
- Recurrence of planar graph limits
- Poisson-Dirichlet branching random walks
- Weak disorder in the stochastic mean-field model of distance. II
- Dynamic space efficient hashing
- Optimal stationary markings
- Eigenvector statistics of Lévy matrices
- Emergence of extended states at zero in the spectrum of sparse random graphs
- Frozen percolation on the binary tree is nonendogenous
- The planted matching problem: phase transitions and exact results
- Unimodular Hausdorff and Minkowski dimensions
- Spectrum of heavy-tailed elliptic random matrices
- Pagerank asymptotics on directed preferential attachment networks
- A conversation with David J. Aldous
- On the speed and spectrum of mean-field random walks among random conductances
- Stable matchings in high dimensions via the Poisson-weighted infinite tree
- Local weak convergence for PageRank
- Interacting diffusions on sparse graphs: hydrodynamics from local weak limits
- Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics
- Parking on a random rooted plane tree
- Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
- Maxima and near-maxima of a Gaussian random assignment field
- Local picture and level-set percolation of the Gaussian free field on a large discrete torus
- Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
- On the expected total number of infections for virus spread on a finite network
- Percolations on random maps. I: Half-plane models
- Degree distribution of shortest path trees and bias of network sampling algorithms
- Maximum independent sets on random regular graphs
- Navigation on a Poisson point process
- Weak disorder asymptotics in the stochastic mean-field model of distance
- Factor models on locally tree-like graphs
- Asymptotic learning on Bayesian social networks
- Weak convergence of finite graphs, integrated density of states and a Cheeger type inequality
- The radial spanning tree of a Poisson point process
- Laws of large numbers in stochastic geometry with statistical applications
- The densest subgraph problem in sparse random graphs
- Asymptotic representation theory and the spectrum of a random geometric graph on a compact Lie group
- The number of accessible paths in the hypercube
- Sparse expanders have negative curvature
- Transitive graphs uniquely determined by their local structure
- The smoothing transform: a review of contraction results
- Least squares approximation to the distribution of project completion times with Gaussian uncertainty
- Distributionally robust mixed integer linear programs: persistency models with applications
- Random infinite squarings of rectangles
- Ground states for exponential random graphs
- Convergence of directed random graphs to the Poisson-weighted infinite tree
- Mean-field monomer-dimer models. A review
- The limiting distributions of large heavy Wigner and arbitrary random matrices
- The minimal spanning tree and the upper box dimension
- On the phase transition in random simplicial complexes
- Interacting particle systems as stochastic social dynamics
- Matchings on infinite graphs
- Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results
- Around the circular law
- Replica symmetry of the minimum matching
- Invasion percolation on the Poisson-weighted infinite tree
- Lévy-Khintchine random matrices and the Poisson weighted infinite skeleton tree
- Random simplicial complexes: around the phase transition
- Renewal sequences and record chains related to multiple zeta sums
- A stochastic complex network model
- Cutting down trees with a Markov chainsaw
- Belief propagation for optimal edge cover in the random complete graph
- Connectivity of random geometric graphs related to minimal spanning forests
- The minimum perfect matching in pseudo-dimension \(0<q<1\)
- Tree convolution for probability distributions with unbounded support
- Random intersection graphs with communities
- Partition functions of discrete coalescents: from Cayley's formula to Frieze's (3) limit theorem
- Invariance, quasi-invariance, and unimodularity for random graphs
- Surprising identities for the greedy independent set on Cayley trees
- Strong couplings for static locally tree-like random graphs
- THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
- Dense peelable random uniform hypergraphs
- Covering a compact space by fixed-radius or growing random balls
- Explosion and linear transit times in infinite trees
- A fractal dimension for measures via persistent homology
- Central limit theorem for statistics of subcritical configuration models
- Parking on a random tree
- Accessibility percolation on random rooted labeled trees
- An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
- Eternal family trees and dynamics on unimodular random graphs
- Shift-coupling of random rooted graphs and networks
- The rank of diluted random graphs
- Spectrum of large random Markov chains: Heavy-tailed weights on the oriented complete graph
- Diameter of the stochastic mean-field model of distance
- Endogeny for the logistic recursive distributional equation
- Entropy of some models of sparse random graphs with vertex-names
- A critical branching process model for biodiversity
- A survey of max-type recursive distributional equations
- A new approach to the orientation of random hypergraphs
- The set of solutions of random XORSAT formulae
- Minimum weight disk triangulations and fillings
This page was built for publication: The objective method: Probabilistic combinatorial optimization and local weak convergence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4450065)
