On random perfect matchings in metric spaces with not-too-large diameters

DOI10.1007/s00224-022-10087-8OpenAlexW4283022102MaRDI QIDQ2158300

Ching-Lueh Chang

Publication date: 26 July 2022

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-022-10087-8

zbMATH Keywords

metric spacetravelling salesman problemsublinear-time algorithmrandom matchingconcentration bound

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Real functions (26-XX) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Las Vegas approximations for metric 1-median selection
• Improved approximation algorithms for metric MaxTSP
• Sublinear time algorithms for metric space problems
• All-pairs shortest paths with a sublinear additive error
• Sublinear‐time approximation algorithms for clustering via random sampling
• Approximate distance oracles
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• Fast Approximation in Subspaces by Doubling Metric Decomposition
• On Approximating the Average Distance Between Points
• Multiembedding of Metric Spaces
• Inequalities: theory of majorization and its applications

This page was built for publication: On random perfect matchings in metric spaces with not-too-large diameters