Buchumschlag

Smoothed Analysis of Online Metric Problems

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Coester, Christian, Umenberger, Jack
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Online Monotone Metric Embeddings
von: Coester, Christian, et al.
Veröffentlicht: (2026)

Online 3-Taxi on General Metrics
von: Coester, Christian, et al.
Veröffentlicht: (2025)

Transposition is Nearly Optimal for IID List Update
von: Coester, Christian
Veröffentlicht: (2026)

Randomized $k$-server in polynomial time
von: Coester, Christian, et al.
Veröffentlicht: (2026)

Chasing Small Sets Optimally Against Adaptive Adversaries
von: Coester, Christian, et al.
Veröffentlicht: (2026)

Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion
von: Li, Yingxi, et al.
Veröffentlicht: (2025)

Online Metric TSP
von: Bertram, Christian
Veröffentlicht: (2025)

Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
von: Bai, Xingjian, et al.
Veröffentlicht: (2024)

Learning-Augmented Priority Queues
von: Benomar, Ziyad, et al.
Veröffentlicht: (2024)

Online Metric Matching: Beyond the Worst Case
von: Yang, Mingwei, et al.
Veröffentlicht: (2024)

Query Complexity of the Metric Steiner Tree Problem
von: Chen, Yu, et al.
Veröffentlicht: (2022)

The Online Submodular Cover Problem
von: Gupta, Anupam, et al.
Veröffentlicht: (2025)

Online Knapsack Problems with Estimates
von: Balabán, Jakub, et al.
Veröffentlicht: (2025)

The Online Submodular Assignment Problem
von: Hathcock, Daniel, et al.
Veröffentlicht: (2024)

The Online Submodular Assignment Problem
von: Hathcock, Daniel, et al.
Veröffentlicht: (2024)

Optimal Smoothed Analysis of the Simplex Method
von: Bach, Eleon, et al.
Veröffentlicht: (2025)

Smoothed Analysis of Dynamic Graph Algorithms
von: Meir, Uri, et al.
Veröffentlicht: (2025)

Effective Traveling for Metric Instances of the Traveling Thief Problem
von: Eube, Jan, et al.
Veröffentlicht: (2026)

Learning-Augmented Online Covering Problems
von: Ameli, Afrouz Jabal, et al.
Veröffentlicht: (2025)

A Multivariate Complexity Analysis of the Generalized Noah's Ark Problem
von: Komusiewicz, Christian, et al.
Veröffentlicht: (2023)

Online Rounding Schemes for $ k $-Rental Problems
von: Nekouyan, Hossein, et al.
Veröffentlicht: (2025)

Nearly Tight Bounds for the Online Sorting Problem
von: Azar, Yossi, et al.
Veröffentlicht: (2025)

Complexity Classes for Online Problems with and without Predictions
von: Berg, Magnus, et al.
Veröffentlicht: (2024)

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem
von: Bläsius, Thomas, et al.
Veröffentlicht: (2025)

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
von: Bartal, Yair, et al.
Veröffentlicht: (2024)

Near-real-time Solutions for Online String Problems
von: Köppl, Dominik, et al.
Veröffentlicht: (2026)

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions
von: Berg, Magnus
Veröffentlicht: (2024)

Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs
von: Azar, Yossi, et al.
Veröffentlicht: (2025)

A New Impossibility Result for Online Bipartite Matching Problems
von: Chierichetti, Flavio, et al.
Veröffentlicht: (2025)

Time Efficient Implementation for Online $k$-server Problem on Trees
von: Khadiev, Kamil, et al.
Veröffentlicht: (2024)

Optimizing Inventory Placement for a Downstream Online Matching Problem
von: Epstein, Boris, et al.
Veröffentlicht: (2024)

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
von: Dinitz, Michael, et al.
Veröffentlicht: (2025)

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
von: Ma, Will, et al.
Veröffentlicht: (2019)

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
von: Bathie, Gabriel, et al.
Veröffentlicht: (2023)

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
von: Bhaskara, Aditya, et al.
Veröffentlicht: (2024)

Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs
von: Moseley, Benjamin, et al.
Veröffentlicht: (2024)

Efficient Online Sensitivity Analysis For The Injective Bottleneck Path Problem
von: Kaymakov, Kirill V., et al.
Veröffentlicht: (2024)

Parsimonious Learning-Augmented Online Metric Matching
von: Shin, Yongho, et al.
Veröffentlicht: (2026)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
von: Driemel, Anne, et al.
Veröffentlicht: (2026)