Stochastic analysis of partitioning algorithms for matching problems

DOI10.1239/JAP/1014842552MaRDI QIDQ4519111zbMATH OpenOpenAlexFDO

Authors Ludger Rüschendorf, G. Sachs

Publication date 30 August 2001

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/314fbf3b794cb02f8fab91548fd8a29adba00422

zbMATH Keywords

dissection algorithmKarp's algorithmoptimal matchingquasiadditive functionals

Mathematics Subject Classification ID

Limit theorems in probability theory (60F99) Analysis of algorithms (68W40)

Recommendations

• Stability and efficiency of partitions in matching problems
• scientific article; zbMATH DE number 52589
• Probabilistic analysis of optimum partitioning
• On the analysis of stochastic divide and conquer algorithms
• Improved analysis of the greedy algorithm for stochastic matching
• Improved approximation algorithms for stochastic matching
• Approximation algorithms for semi-random partitioning problems
• Analysis of algorithms for a class of continuous partition problems
• On the two-stage stochastic graph partitioning problem

Cited in

(3)

• Partitions-requirements-matrices as optimal Markov kernels of special stochastic dynamic distance optimal partitioning problems
• On the weighted Euclidean matching problem in R^d
• Partitioning heuristics for two geometric maximization problems

This page was built for publication: Stochastic analysis of partitioning algorithms for matching problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4519111)