The ?(2) limit in the random assignment problem
From MaRDI portal
Publication:2746215
DOI10.1002/rsa.1015zbMath0993.60018arXivmath/0010063WikidataQ90157006 ScholiaQ90157006MaRDI QIDQ2746215
Publication date: 15 September 2002
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0010063
Related Items
Lévy-Khintchine random matrices and the Poisson weighted infinite skeleton tree, Random Simplicial Complexes: Around the Phase Transition, Bounds for Random Binary Quadratic Programs, On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph, A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment, Branching Process Approach for 2-Sat Thresholds, The random fractional matching problem, Random multi-index matching problems, The Effect of Adding Randomly Weighted Edges, The minimum perfect matching in pseudo-dimension 0 < q < 1, The Random QUBO, Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities, Aligning random graphs with a sub-tree similarity message-passing algorithm, Efficient algorithms for three‐dimensional axial and planar random assignment problems, The number of matchings in random graphs, On the number ofk-cycles in the assignment problem for random matrices, Diameter of the Stochastic Mean-Field Model of Distance, Scaling and universality in continuous length combinatorial optimization, Minimum weight disk triangulations and fillings, The Dyck bound in the concave 1-dimensional random assignment model, On the Maximum of a Special Random Assignment Process, The planted matching problem: sharp threshold and infinite-order phase transition, Heavy and light paths and Hamilton cycles, The cost of strategy-proofness in school choice, The densest subgraph problem in sparse random graphs, Distributionally robust mixed integer linear programs: persistency models with applications, On the phase transition in random simplicial complexes, Replica symmetry of the minimum matching, Belief propagation for optimal edge cover in the random complete graph, Endogeny for the logistic recursive distributional equation, A survey of max-type recursive distributional equations, The mean field traveling salesman and related problems, Near-minimal spanning trees: A scaling exponent in probability models, Properties of atypical graphs from negative complexities, Rounding of continuous random variables and oscillatory asymptotics, Asymptotic behavior of the expected optimal value of the multidimensional assignment problem, Random assignment problems, On the hardness of sampling independent sets beyond the tree threshold, Sequential cavity method for computing free energy and surface pressure, An assignment problem at high temperature, A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming, Weak disorder in the stochastic mean-field model of distance. II, On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model, Random assignment problems on \(2d\) manifolds, Strong and weighted matchings in inhomogenous random graphs, The planted matching problem: phase transitions and exact results, A conversation with David J. Aldous, Typical values of extremal-weight combinatorial structures with independent symmetric weights, Exploiting partial correlations in distributionally robust optimization, The stable marriage problem: an interdisciplinary review from the physicist's perspective, Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs, Maxima and near-maxima of a Gaussian random assignment field, A general method for lower bounds on fluctuations of random variables, On the longest path of a randomly weighted tournament, Maximum independent sets on random regular graphs, A diluted version of the perceptron model, Local tail bounds for functions of independent random variables, An asymptotical study of combinatorial optimization problems by means of statistical mechanics, On the maximum of random assignment process, Weighted enumeration of spanning subgraphs in locally tree-like graphs, Minimum Cost Matching in a Random Graph with Random Costs, The Blind Passenger and the Assignment Problem, First-passage percolation on a ladder graph, and the path cost in a VCG auction, Weight of a link in a shortest path tree and the Dedekind Eta function, Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle, Successive shortest paths in complete graphs with random edge weights, Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections, Invariant probability measures and dynamics of exponential linear type maps, On the survey-propagation equations in random constraint satisfiability problems
Cites Work
- On the value of a random minimum spanning tree problem
- Huge random structures and mean field models for spin glasses
- Asymptotics in the random assignment problem
- The stochastic traveling salesman problem: finite size scaling and the cavity prediction
- Certain expected values in the random assignment problem
- On the Expected Value of a Random Assignment Problem
- On linear programs with random costs
- A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
- A random tree model associated with random graphs
- Constructive bounds and exact expectations for the random assignment problem
- The percolation process on a tree where infinite clusters are frozen
- Exact solution of the random bipartite matching model
- A Lower Bound on the Expected Cost of an Optimal Assignment
