Imagen de Portada

Online Metric Matching: Beyond the Worst Case

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Yang, Mingwei, Yu, Sophie H.
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion
por: Li, Yingxi, et al.
Publicado: (2025)

Beyond Worst Case Local Computation Algorithms
por: Biswas, Amartya Shankha, et al.
Publicado: (2024)

Optimal Static Dictionary with Worst-Case Constant Query Time
por: Hu, Yang, et al.
Publicado: (2024)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
por: Abboud, Amir, et al.
Publicado: (2024)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
por: Silwal, Sandeep, et al.
Publicado: (2025)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
por: Navarro, Gonzalo
Publicado: (2024)

Dynamic Set Cover with Worst-Case Recourse
por: Solomon, Shay, et al.
Publicado: (2025)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
por: Meierhans, Simon, et al.
Publicado: (2025)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
por: Meierhans, Simon, et al.
Publicado: (2025)

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

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
por: Bhattacharya, Sayan, et al.
Publicado: (2025)

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

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
por: Bansal, Nikhil, et al.
Publicado: (2024)

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
por: van der Hoog, Ivor, et al.
Publicado: (2025)

Online Metric TSP
por: Bertram, Christian
Publicado: (2025)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
por: Grilnberger, Mara, et al.
Publicado: (2026)

Online Monotone Metric Embeddings
por: Coester, Christian, et al.
Publicado: (2026)

Count-Min Sketch with Conservative Updates: Worst-Case Analysis
por: Mazziane, Younes Ben, et al.
Publicado: (2024)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
por: Haeupler, Bernhard, et al.
Publicado: (2024)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
por: Mao, Xiao
Publicado: (2023)

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

Maximal Biclique Enumeration with Improved Worst-Case Time Complexity Guarantee: A Partition-Oriented Strategy
por: Wang, Kaixin, et al.
Publicado: (2026)

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

Availability is all you need: achieving optimal regret with minimal information for dynamic matching
por: Kerimov, Süleyman, et al.
Publicado: (2025)

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

Online Matching: A Brief Survey
por: Huang, Zhiyi, et al.
Publicado: (2024)

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

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

Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space
por: Jang, Jihoon, et al.
Publicado: (2025)

From Amortized to Worst Case Delay in Enumeration Algorithms
por: Capelli, Florent, et al.
Publicado: (2021)

Almost Tight Bounds for Online Hypergraph Matching
por: Tröbst, Thorben, et al.
Publicado: (2024)

Online Matching with Delays and Size-based Costs
por: Kawase, Yasushi, et al.
Publicado: (2024)

Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching
por: Ma, Will
Publicado: (2024)

The Power of Greedy for Online Minimum Cost Matching on the Line
por: Balkanski, Eric, et al.
Publicado: (2022)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
por: Joseph, et al.
Publicado: (2023)

Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis
por: Jiang, Minhui, et al.
Publicado: (2024)

Hypergraph Samplers: Typical and Worst Case Behavior
por: Alev, Vedat Levi, et al.
Publicado: (2026)

Triangle Detection in Worst-Case Sparse Graphs via Local Sketching
por: Duan, Hongyi, et al.
Publicado: (2025)

Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum
por: Sun, Enze, et al.
Publicado: (2025)