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