Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
From MaRDI portal
Publication:1262767
DOI10.1007/BF02124678zbMath0686.68039OpenAlexW2610893972MaRDI QIDQ1262767
Publication date: 1989
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02124678
upper boundsaverage case analysis of algorithmsminimax grid matching problemdimensional bin packingdimensional on-line bin packingline dynamic allocationmaximum up-right matching problem
Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Discrete mathematics in relation to computer science (68R99)
Related Items
On the quadratic random matching problem in two-dimensional domains, Linear waste of best fit bin packing on skewed distributions, Constructions of majorizing measures, Bernoulli processes and cotype, The average-case analysis of some on-line algorithms for bin packing, The spectrum of a random geometric graph is concentrated, Optimal Cheeger cuts and bisections of random geometric graphs, On the spectrum of dense random geometric graphs, Optimal Matching and Empirical Measures, Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds, Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures, Correlation length of the two-dimensional random field Ising model via greedy lattice animal, Belief Propagation for MiniMax Weight Matching, Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator, Decomposing Random Permutations into Order-Isomorphic Subpermutations, Long range order for random field Ising and Potts models, Dilation bootstrap, Gravitational allocation for uniform points on the sphere, Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle, Average-case analyses of first fit and random fit bin packing, Packings in two dimensions: Asymptotic average-case analysis of algorithms, Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures, Average-case performance analysis of a 2D strip packing algorithm -- NFDH, Monotone properties of random geometric graphs have sharp thresholds, Properly-weighted graph Laplacian for semi-supervised learning, Gravitational allocation to Poisson points, A variational approach to the consistency of spectral clustering, Analysis of Stochastic Online Bin Packing Processes, A provably efficient algorithm for dynamic storage allocation, On optimal matching of Gaussian samples, Analysis of $p$-Laplacian Regularization in Semisupervised Learning, On the rate of convergence of empirical measure in $\infty $-Wasserstein distance for unbounded density function, A simple Fourier analytic proof of the AKT optimal matching theorem, Exact Bounds for the Stochastic Upward Matching Problem, Exact Bounds for the Stochastic Upward Matching Problem, Transport inequalities on Euclidean spaces for non-Euclidean metrics, Bin Packing with Queues, Unnamed Item, Continuum limit of total variation on point clouds
Cites Work
- Unnamed Item
- A provably efficient algorithm for dynamic storage allocation
- On optimal matchings
- Polymorphic arrays: A novel VLSI layout for systolic computers
- The average-case analysis of some on-line algorithms for bin packing
- The empirical discrepancy over lower layers and a related law of large numbers
- Limit properties of random variables associated with a partial ordering of \(R^d\)
- On large deviations of the empiric D.F. of vector chance variables and a law of the iterated logarithm
- Wafer-Scale Integration of Systolic Arrays
- Empirical and Poisson processes on classes of sets or functions too large for central limit theorems
- Necessary and Sufficient Conditions for the Uniform Convergence of Means to their Expectations
- On Representatives of Subsets
- Irregularities of distribution, VII
- On the Convergence of Empiric Distribution Functions
