Random restricted matching and lower bounds for combinatorial optimization
From MaRDI portal
Publication:1928532
DOI10.1007/S10878-011-9384-4zbMATH Open1282.90156OpenAlexW2154146365MaRDI QIDQ1928532FDOQ1928532
Authors: Stefan Steinerberger 
Publication date: 3 January 2013
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-011-9384-4
Recommendations
- Optimal random matchings, tours, and spanning trees in hierarchically separated trees
- Optimal Random Matchings on Trees and Applications
- Combinatorial Optimization Over Two Random Point Sets
- Euclidean semi-matchings of random samples
- Convergence of asymptotic costs for random Euclidean matching problems
uniform distributionminimal spanning treepacking problemstraveling salesmanrestricted matchingVoronoi decomposition
Cites Work
- On optimal matchings
- Sequences, discrepancies and applications
- The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
- Title not available (Why is that?)
- A First Course in Order Statistics
- On irregularities of distribution
- Box integrals
- Title not available (Why is that?)
- Title not available (Why is that?)
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- Growth rates of Euclidean minimal spanning trees with power weighted edges
- Extremal uniform distribution and random chord lengths
- Advances in the theory of box integrals
- Shortest Paths Through Pseudo-Random Points in the d-Cube
- A new lower bound for the geometric traveling salesman problem in terms of discrepancy
- Title not available (Why is that?)
- Discrepancy and distance between sets
- Concerning $\int_0^1 \cdots \int_0^1 {(x_1^2 + \cdots + x_k^2 )} ^{{1 / 2}} dx_1 \cdots ,dx_k $ and a Taylor Series Method
Cited In (8)
- Exact Bounds for the Stochastic Upward Matching Problem
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Optimal Random Matchings on Trees and Applications
- On the arrangement of point sets in the unit interval
- Randomized Post-optimization for t-Restrictions
- On the complexity of minimum maximal uniquely restricted matching
- Optimal random matchings, tours, and spanning trees in hierarchically separated trees
- Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory
This page was built for publication: Random restricted matching and lower bounds for combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1928532)
