:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Gupta, Anupam, Traub, Vera
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2511.18460
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Bidirected Cut Relaxation for Steiner Tree: Better Integrality Gap Bounds and the Limits of Moat Growing
by: Paschmanns, Paul, et al.
Published: (2026)

On the Bidirected Cut Relaxation for Steiner Forest
by: Byrka, Jarosław, et al.
Published: (2024)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
by: Byrka, Jarosław, et al.
Published: (2024)

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
by: Christalla, Manuel, et al.
Published: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
by: Neuwohner, Meike, et al.
Published: (2025)

2-Approximation for Prize-Collecting Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2023)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2024)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2025)

A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
by: Neuwohner, Meike, et al.
Published: (2025)

Online Steiner Forest with Recourse
by: Long, Yaowei, et al.
Published: (2026)

A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
by: Hommelsheim, Felix, et al.
Published: (2025)

A Better-Than-1.6-Approximation for Prize-Collecting TSP
by: Blauth, Jannis, et al.
Published: (2023)

Streaming Algorithms for Geometric Steiner Forest
by: Czumaj, Artur, et al.
Published: (2020)

Approximation Algorithms for Steiner Connectivity Augmentation
by: Hathcock, Daniel, et al.
Published: (2023)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
by: Feldmann, Andreas Emil, et al.
Published: (2024)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Prize-Collecting Steiner Tree: A 1.79 Approximation
by: Ahmadi, Ali, et al.
Published: (2024)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
by: Grandoni, Fabrizio, et al.
Published: (2026)

The Online Submodular Cover Problem
by: Gupta, Anupam, et al.
Published: (2025)

Fully-Dynamic Submodular Cover with Bounded Recourse
by: Gupta, Anupam, et al.
Published: (2020)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
by: Swamy, Chaitanya, et al.
Published: (2025)

A Learning Perspective on Random-Order Covering Problems
by: Gupta, Anupam, et al.
Published: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks
by: Blauth, Jannis, et al.
Published: (2022)

3/2-Approximation for the Forest Augmentation Problem
by: Çivril, Ali
Published: (2024)

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

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
by: Chekuri, Chandra, et al.
Published: (2024)

Random Order Set Cover is as Easy as Offline
by: Gupta, Anupam, et al.
Published: (2021)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
by: Disser, Yann, et al.
Published: (2024)

The Steiner Path Aggregation Problem
by: Chen, Da Qi, et al.
Published: (2025)

Multi-Level Steiner Trees
by: Ahmed, Reyan, et al.
Published: (2018)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Improved 2-Approximate Shortest Paths for close vertex pairs
by: Gupta, Manoj
Published: (2025)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

The Steiner Shortest Path Tree Problem
by: Asher, Omer, et al.
Published: (2025)

Optimal Sensitivity Oracle for Steiner Mincut
by: Bhanja, Koustav
Published: (2024)

Graph Spanners for Group Steiner Distances
by: Bilò, Davide, et al.
Published: (2024)

DAG Covers: The Steiner Point Effect
by: Bhore, Sujoy, et al.
Published: (2026)

Steiner Forest for $H$-Subgraph-Free Graphs
by: Eagling-Vose, Tala, et al.
Published: (2026)

On Approximability of Steiner Tree in $\ell_p$-metrics
by: Fleischmann, Henry, et al.
Published: (2023)