Buchumschlag

3/2-Approximation for the Forest Augmentation Problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Çivril, Ali
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

4/3-Approximation of Graphic TSP
von: Çivril, Ali
Veröffentlicht: (2023)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
von: Çivril, Ali
Veröffentlicht: (2023)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
von: Çivril, Ali
Veröffentlicht: (2024)

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

A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

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

Prize-Collecting Forest with Submodular Penalties: Improved Approximation
von: Ahmadi, Ali, et al.
Veröffentlicht: (2025)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
von: Dong, Yinhao, et al.
Veröffentlicht: (2024)

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

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

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

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

On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
von: Albers, Susanne, et al.
Veröffentlicht: (2025)

Hardness and Approximation Algorithms for Balanced Districting Problems
von: Dharangutte, Prathamesh, et al.
Veröffentlicht: (2025)

Improved Approximations for Dial-a-Ride Problems
von: Zhao, Jingyang, et al.
Veröffentlicht: (2026)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2020)

Optimal 4-Approximation for the Correlated Pandora's Problem
von: Bansal, Nikhil, et al.
Veröffentlicht: (2025)

New Approximation Guarantees for The Inventory Staggering Problem
von: Alon, Noga, et al.
Veröffentlicht: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

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

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

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2026)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
von: Chen, Yong, et al.
Veröffentlicht: (2025)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

A Simple 4-Approximation Algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees
von: Dempsey, Jordan, et al.
Veröffentlicht: (2024)

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

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
von: Buchem, Moritz, et al.
Veröffentlicht: (2024)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
von: Chen, Lin, et al.
Veröffentlicht: (2026)

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

Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
von: Dai, Han, et al.
Veröffentlicht: (2025)

A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
von: Saller, Sophia, et al.
Veröffentlicht: (2023)

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

Improved Approximation Ratios for the Shortest Common Superstring Problem with Reverse Complements
von: Yamano, Ryosuke, et al.
Veröffentlicht: (2026)

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2026)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Approximating Energy-Constrained Drone Delivery Packing Problem for Last-Mile Logistics
von: Jana, Saswata, et al.
Veröffentlicht: (2026)

Approximations for the Weighted Reversal, Transposition, and Indel Distance Problem with Intergenic Region Information
von: Siqueira, Gabriel, et al.
Veröffentlicht: (2025)