Buchumschlag

Complexity Classes for Online Problems with and without Predictions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Berg, Magnus, Boyar, Joan, Favrholdt, Lene M., Larsen, Kim S.
Format:	Preprint
Veröffentlicht:	2024
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 Interval Scheduling with Predictions
von: Boyar, Joan, et al.
Veröffentlicht: (2023)

Forwarding Packets Greedily
von: Boyar, Joan, et al.
Veröffentlicht: (2026)

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

Distributed Graph Algorithms with Predictions
von: Boyar, Joan, et al.
Veröffentlicht: (2025)

On the Online Weighted Non-Crossing Matching Problem
von: Boyar, Joan, et al.
Veröffentlicht: (2026)

Online Bin Covering with Frequency Predictions
von: Berg, Magnus, et al.
Veröffentlicht: (2024)

Parameterized Complexity of MinCSP over the Point Algebra
von: Osipov, George, et al.
Veröffentlicht: (2023)

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)

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)

Smoothed Analysis of Online Metric Problems
von: Coester, Christian, et al.
Veröffentlicht: (2025)

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

On the Complexity of Secluded Path Problems
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2026)

On the Advice Complexity of Online Matching on the Line
von: Csaba, Béla, et al.
Veröffentlicht: (2024)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
von: Mallek, Nadym, et al.
Veröffentlicht: (2025)

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)

Towards Settling the Complexity of the Lettericity Problem
von: Grobler, Mario, et al.
Veröffentlicht: (2026)

Computational Complexity of the Interval Ordering Problem
von: Pawlowski, Simeon, et al.
Veröffentlicht: (2026)

New Results on a General Class of Minimum Norm Optimization Problems
von: Chen, Kuowen, et al.
Veröffentlicht: (2025)

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

The Parameterized Complexity Landscape of the Unsplittable Flow Problem
von: Ganian, Robert, et al.
Veröffentlicht: (2024)

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

On the Complexity of Distributed Edge Coloring and Orientation Problems
von: Brandt, Sebastian, et al.
Veröffentlicht: (2025)

Algorithms and Complexity of Hedge Cluster Deletion Problems
von: Konstantinidis, Athanasios L., et al.
Veröffentlicht: (2025)

Forbidden Subgraph Problems with Predictions
von: Böckenhauer, Hans-Joachim, 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)

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)

Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming
von: Flin, Maxime, et al.
Veröffentlicht: (2026)

Faster Dynamic $(Δ+1)$-Coloring Against Adaptive Adversaries
von: Flin, Maxime, et al.
Veröffentlicht: (2025)

Two Complexity Results on Spanning-Tree Congestion Problems
von: Atalig, Sunny, et al.
Veröffentlicht: (2026)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
von: Chen, Yong, 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)

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

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

Space Complexity of Minimum Cut Problems in Single-Pass Streams
von: Ding, Matthew, et al.
Veröffentlicht: (2024)

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