Cover Image

Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Yingxi, Vitercik, Ellen, Yang, Mingwei
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Metric Matching: Beyond the Worst Case
by: Yang, Mingwei, et al.
Published: (2024)

Smoothed Analysis of Online Metric Problems
by: Coester, Christian, et al.
Published: (2025)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
by: Hayderi, Alexandre, et al.
Published: (2024)

Online Metric TSP
by: Bertram, Christian
Published: (2025)

Online 3-Taxi on General Metrics
by: Coester, Christian, et al.
Published: (2025)

Parsimonious Learning-Augmented Online Metric Matching
by: Shin, Yongho, et al.
Published: (2026)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
by: Bakshi, Ainesh, et al.
Published: (2023)

Online Monotone Metric Embeddings
by: Coester, Christian, et al.
Published: (2026)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
by: Bhore, Sujoy, et al.
Published: (2023)

Bi-Criteria Metric Distortion
by: Banihashem, Kiarash, et al.
Published: (2024)

Algorithms with Calibrated Machine Learning Predictions
by: Shen, Judy Hanwen, et al.
Published: (2025)

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
by: Bartal, Yair, et al.
Published: (2024)

Clustering in Varying Metrics
by: Chakrabarty, Deeparnab, et al.
Published: (2025)

Highway Dimension: a Metric View
by: Feldmann, Andreas Emil, et al.
Published: (2024)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
by: Braverman, Mark, et al.
Published: (2024)

Streaming Max-Cut in General Metrics
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Distortion of Metric Voting with Bounded Randomness
by: Cai, Ziyi, et al.
Published: (2026)

Fitting Tree Metrics and Ultrametrics in Data Streams
by: Carmel, Amir, et al.
Published: (2025)

Spanning and Metric Tree Covers Parameterized by Treewidth
by: Elkin, Michael, et al.
Published: (2025)

Query Complexity of the Metric Steiner Tree Problem
by: Chen, Yu, et al.
Published: (2022)

Dynamic Metric Embedding into $\ell_p$ Space
by: Banihashem, Kiarash, et al.
Published: (2024)

An Improved Approximation Algorithm for Metric Triangle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

An Improved Greedy Approximation for (Metric) $k$-Means
by: Charikar, Moses, et al.
Published: (2026)

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
by: Liu, Yang P.
Published: (2024)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
by: Zhao, Jingyang, et al.
Published: (2025)

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
by: Ren, Kinter, et al.
Published: (2024)

Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
by: Mo, Guanlin, et al.
Published: (2024)

Effective Traveling for Metric Instances of the Traveling Thief Problem
by: Eube, Jan, et al.
Published: (2026)

Metric Distortion of Line-up Elections: The Right Person for the Right Job
by: Jerrett, Christopher, et al.
Published: (2024)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
by: Azarmehr, Amir, et al.
Published: (2024)

Online Matching: A Brief Survey
by: Huang, Zhiyi, et al.
Published: (2024)

On the Advice Complexity of Online Matching on the Line
by: Csaba, Béla, et al.
Published: (2024)

Online Matching in Geometric Random Graphs
by: Sentenac, Flore, et al.
Published: (2023)

New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets
by: Prasad, Siddharth, et al.
Published: (2024)

Calculation of the Comparative Efficiency of Algorithms Using a Single Metric
by: Chakraborty, Arya
Published: (2024)

Degree-bounded Online Bipartite Matching: OCS vs. Ranking
by: Feng, Yilong, et al.
Published: (2025)

Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem
by: Bläsius, Thomas, et al.
Published: (2025)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)