Buchumschlag

Stronger adversaries grow cheaper forests: online node-weighted Steiner problems

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Borst, Sander, Eliáš, Marek, Venzin, Moritz
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

To buy or not to buy: deterministic rent-or-buy problems on node-weighted graphs
von: Borst, Sander, et al.
Veröffentlicht: (2025)

Improved Online Load Balancing in the Two-Norm
von: Borst, Sander, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Combinatorial Optimization with Predictions
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2024)

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

Beyond the Half-Approximation: Fair and Efficient Online Class Matching
von: Borst, Sander, et al.
Veröffentlicht: (2026)

Online Matching on $3$-Uniform Hypergraphs
von: Borst, Sander, et al.
Veröffentlicht: (2024)

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

A nearly optimal randomized algorithm for explorable heap selection
von: Borst, Sander, et al.
Veröffentlicht: (2022)

Fast decremental tree sums in forests
von: Berendsohn, Benjamin Aram, et al.
Veröffentlicht: (2026)

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Fast online node labeling with graph subsampling
von: Huang, Yushen, et al.
Veröffentlicht: (2025)

The Steiner Path Aggregation Problem
von: Chen, Da Qi, et al.
Veröffentlicht: (2025)

Multi-Level Steiner Trees
von: Ahmed, Reyan, et al.
Veröffentlicht: (2018)

Online Steiner Forest with Recourse
von: Long, Yaowei, et al.
Veröffentlicht: (2026)

Terminal Steiner tree problem : Complexity and Algorithms
von: S, Jyothish, et al.
Veröffentlicht: (2026)

Optimal Sensitivity Oracle for Steiner Mincut
von: Bhanja, Koustav
Veröffentlicht: (2024)

Graph Spanners for Group Steiner Distances
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

The Steiner Shortest Path Tree Problem
von: Asher, Omer, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Steiner Connectivity Augmentation
von: Hathcock, Daniel, et al.
Veröffentlicht: (2023)

Streaming Algorithms for Geometric Steiner Forest
von: Czumaj, Artur, et al.
Veröffentlicht: (2020)

DAG Covers: The Steiner Point Effect
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)

Lower Bounds on $0$-Extension with Steiner Nodes
von: Chen, Yu, et al.
Veröffentlicht: (2024)

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

2-Approximation for Prize-Collecting Steiner Forest
von: Ahmadi, Ali, et al.
Veröffentlicht: (2023)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
von: Chen, Yu, et al.
Veröffentlicht: (2026)

Finding 4-Additive Spanners: Faster, Stronger, and Simpler
von: Qi, Chuhan
Veröffentlicht: (2025)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
von: Feldmann, Andreas Emil, et al.
Veröffentlicht: (2024)

Parameterized Algorithms for the Steiner Arborescence Problem on a Hypercube
von: Mahapatra, Sugyani, et al.
Veröffentlicht: (2021)

Prize-Collecting Steiner Tree: A 1.79 Approximation
von: Ahmadi, Ali, et al.
Veröffentlicht: (2024)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Sublinear Metric Steiner Forest via Maximal Independent Set
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
von: Bhanja, Koustav, et al.
Veröffentlicht: (2025)

Steiner Forest: A Simplified Better-Than-2 Approximation
von: Gupta, Anupam, et al.
Veröffentlicht: (2025)

Cost-Distance Steiner Trees for Timing-Constrained Global Routing
von: Held, Stephan, et al.
Veröffentlicht: (2025)

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

On the adversarial robustness of Locality-Sensitive Hashing in Hamming space
von: Kapralov, Michael, et al.
Veröffentlicht: (2024)

Faster algorithms for packing forests in graphs and related problems
von: Arkhipov, Pavel, et al.
Veröffentlicht: (2024)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2024)

On computing approximate Lewis weights
von: Apers, Simon, et al.
Veröffentlicht: (2024)

An adversarially robust data-market for spatial, crowd-sourced data
von: Kharman, Aida Manzano, et al.
Veröffentlicht: (2022)