Imagen de Portada

A Better-Than-2 Approximation for the Directed Tree Augmentation Problem

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Neuwohner, Meike, Silina, Olha, Zlatin, Michael
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A $\frac{4}{3}$-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs
por: Neuwohner, Meike
Publicado: (2024)

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

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

Lattice Structure and Efficient Basis Construction for Strongly Connected Orientations
por: Liu, Siyue, et al.
Publicado: (2026)

Steiner Forest: A Simplified Better-Than-2 Approximation
por: Gupta, Anupam, et al.
Publicado: (2025)

The Online Submodular Assignment Problem
por: Hathcock, Daniel, et al.
Publicado: (2024)

The Online Submodular Assignment Problem
por: Hathcock, Daniel, et al.
Publicado: (2024)

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
por: Arndt, Stephen, et al.
Publicado: (2026)

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

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

Efficiently Coloring the Intersection of a General Matroid and Partition Matroids
por: Arndt, Stephen, et al.
Publicado: (2025)

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

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

Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
por: Bampis, Evripidis, et al.
Publicado: (2024)

A New Approach for Approximating Directed Rooted Networks
por: Cohen, Sarel, et al.
Publicado: (2024)

On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
por: Albers, Susanne, et al.
Publicado: (2025)

Approximating Directed Connectivity in Almost-Linear Time
por: Quanrud, Kent
Publicado: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
por: Górkiewicz, Adam, et al.
Publicado: (2025)

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
por: Dinitz, Michael, et al.
Publicado: (2025)

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

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
por: Jiang, Yonggang, et al.
Publicado: (2025)

Hardness and Approximation Algorithms for Balanced Districting Problems
por: Dharangutte, Prathamesh, et al.
Publicado: (2025)

Optimal 4-Approximation for the Correlated Pandora's Problem
por: Bansal, Nikhil, et al.
Publicado: (2025)

New Approximation Guarantees for The Inventory Staggering Problem
por: Alon, Noga, et al.
Publicado: (2025)

Improved Approximations for Dial-a-Ride Problems
por: Zhao, Jingyang, et al.
Publicado: (2026)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
por: Antoniadis, Antonios, et al.
Publicado: (2020)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
por: Dong, Yinhao, et al.
Publicado: (2024)

Learning-Augmented Online Covering Problems
por: Ameli, Afrouz Jabal, et al.
Publicado: (2025)

Balancing Weights, Directed Sparsification, and Augmenting Paths
por: Li, Jason
Publicado: (2026)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
por: Zhao, Jingyang, et al.
Publicado: (2025)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
por: Bentert, Matthias, et al.
Publicado: (2025)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
por: Chen, Yong, et al.
Publicado: (2025)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
por: Zhao, Jingyang, et al.
Publicado: (2025)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
por: Zhao, Jingyang, et al.
Publicado: (2026)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
por: Ashvinkumar, Vikrant, et al.
Publicado: (2024)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
por: Mallek, Nadym, et al.
Publicado: (2025)

Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
por: Zhao, Jingyang, et al.
Publicado: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
por: Dai, Han, et al.
Publicado: (2025)

Approximating Traveling Salesman Problems Using a Bridge Lemma
por: Böhm, Martin, et al.
Publicado: (2024)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
por: Chen, Lin, et al.
Publicado: (2026)