Buchumschlag

Maintaining Random Assignments under Adversarial Dynamics

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Haeupler, Bernhard, Paramonov, Anton
Format:	Preprint
Veröffentlicht:	2026
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

Maintaining Routing Structures under Deletions via Self-Pruning
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

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

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

DAG Projections: Reducing Distance and Flow Problems to DAGs
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

New Structures and Algorithms for Length-Constrained Expander Decompositions
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2024)

Dynamic Construction of the Lovász Local Lemma
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

Near-Optimal Directed Low-Diameter Decompositions
von: Bringmann, Karl, et al.
Veröffentlicht: (2025)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Simple Length-Constrained Expander Decompositions
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Low-Step Multi-Commodity Flow Emulators
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2024)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

A Cut-Matching Game for Constant-Hop Expanders
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2022)

Maintaining $k$-MinHash Signatures over Fully-Dynamic Data Streams with Recovery
von: Clementi, Andrea, et al.
Veröffentlicht: (2024)

Clustering with Label Consistency
von: Chakraborty, Diptarka, et al.
Veröffentlicht: (2025)

Reviving Thorup's Shortcut Conjecture
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Dynamically Maintaining the Persistent Homology of Time Series
von: di Montesano, Sebastiano Cultrera, et al.
Veröffentlicht: (2023)

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

Online Facility Assignments on Polygons
von: Malik, Sumaiya, et al.
Veröffentlicht: (2025)

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

Maintaining Bipartite Colourings on Temporal Graphs on a Budget
von: Adamson, Duncan, et al.
Veröffentlicht: (2025)

Generalized Assignment and Knapsack Problems in the Random-Order Model
von: Klimm, Max, et al.
Veröffentlicht: (2025)

Memory Bounds for Concurrent Bounded Queues
von: Aksenov, Vitaly, et al.
Veröffentlicht: (2021)

Weighted Chairman Assignment and Flow-Time Scheduling
von: Liu, Siyue, et al.
Veröffentlicht: (2025)

Randomized Rounding over Dynamic Programs
von: Bamas, Etienne, et al.
Veröffentlicht: (2025)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
von: Dughmi, Shaddin, et al.
Veröffentlicht: (2025)

Multi-Slot Tag Assignment Problem in Billboard Advertisement
von: Ali, Dildar, et al.
Veröffentlicht: (2024)

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

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
von: Banihashem, Kiarash, et al.
Veröffentlicht: (2025)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Efficient Resource Allocation under Adversary Attacks: A Decomposition-Based Approach
von: Davoodi, Mansoor, et al.
Veröffentlicht: (2025)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
von: Bukov, Anton, et al.
Veröffentlicht: (2023)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
von: Buchbinder, Niv, et al.
Veröffentlicht: (2026)

Bin Packing under Random-Order: Breaking the Barrier of 3/2
von: Hebbar, Anish, et al.
Veröffentlicht: (2024)