Buchumschlag

A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Kortsarz, Guy
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A (1.999999)-approximation ratio for vertex cover problem
von: Zohrehbandian, Majid
Veröffentlicht: (2024)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
von: Colli, Giordano
Veröffentlicht: (2025)

Simple approximation algorithms for Polyamorous Scheduling
von: Biktairov, Yuriy, et al.
Veröffentlicht: (2024)

Singleton algorithms for the Constraint Satisfaction Problem
von: Zhuk, Dmitriy
Veröffentlicht: (2025)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

On the Complexity of Problems on Tree-structured Graphs
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2022)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
von: Gur, Tom, et al.
Veröffentlicht: (2025)

On the approximability of graph visibility problems
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

An approximation notion between P and FPTAS
von: Bismuth, Samuel, et al.
Veröffentlicht: (2026)

Sketching approximability of all finite CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

Hardness of clique approximation for monotone circuits
von: Błasiok, Jarosław, et al.
Veröffentlicht: (2025)

A Strong Direct Sum Theorem for Distributional Query Complexity
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

On Computability of Computable Problems
von: Khaliq, Asad
Veröffentlicht: (2023)

The Stochastic Arrival Problem
von: Webster, Thomas
Veröffentlicht: (2022)

A near-optimal Quadratic Goldreich-Levin algorithm
von: Briët, Jop, et al.
Veröffentlicht: (2025)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
von: Bender, Matías, et al.
Veröffentlicht: (2025)

Efficient algorithms for collecting the statistics of large-scale IP address data
von: Liu, Hui, et al.
Veröffentlicht: (2021)

Continuous Defensive Domination Problems
von: Grüne, Christoph, et al.
Veröffentlicht: (2026)

The Greedy Coin Change Problem
von: Gupta, Shreya, et al.
Veröffentlicht: (2024)

On the Hardness of the Drone Delivery Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2025)

Local vs. Global Interpretability: A Computational Complexity Perspective
von: Bassan, Shahaf, et al.
Veröffentlicht: (2024)

Hunting a rabbit: complexity, approximability and some characterizations
von: Ben-Ameur, Walid, et al.
Veröffentlicht: (2025)

Parameterized Complexity of the Star Decomposition Problem
von: Hajebi, Sahab, et al.
Veröffentlicht: (2024)

Reductions Between Code Equivalence Problems
von: Cheraghchi, Mahdi, et al.
Veröffentlicht: (2025)

Total Search Problems in $\mathsf{ZPP}$
von: Fleming, Noah, et al.
Veröffentlicht: (2025)

The 2-Attractor Problem is NP-Complete
von: Fuchs, Janosch, et al.
Veröffentlicht: (2023)

Inverse Intersections for Boolean Satisfiability Problems
von: Homer, Paul W.
Veröffentlicht: (2025)

On the Exact Matching Problem in Dense Graphs
von: Maalouly, Nicolas El, et al.
Veröffentlicht: (2024)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
von: Bennett, Huck, et al.
Veröffentlicht: (2022)

Sketching approximations and LP approximations for finite CSPs are related
von: Singer, Noah G., et al.
Veröffentlicht: (2025)

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
von: Le, Tran Duy Anh, et al.
Veröffentlicht: (2024)

Maximum Matching and Related Problems in Catalytic Logspace
von: Chakraborty, Srijan, et al.
Veröffentlicht: (2026)

Strong Inapproximability for a Promise Rank Problem
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2026)

The Line Traveling Salesman and Repairman Problem with Collaboration
von: Golak, Julian, et al.
Veröffentlicht: (2025)

No Complete Problem for Constant-Cost Randomized Communication
von: Fang, Yuting, et al.
Veröffentlicht: (2024)

P-time Algorithms for Typical #EO Problems
von: Meng, Boning, et al.
Veröffentlicht: (2024)

Explaining the Ubiquity of Phase Transitions in Decision Problems
von: Jackson, Andrew
Veröffentlicht: (2025)

An Efficient Algorithm for Solving the 2-MAXSAT Problem
von: Chen, Yangjun
Veröffentlicht: (2023)

Geometry Of The Subset Sum Problem -- Part I
von: Bollepalli, Srinivas Balaji
Veröffentlicht: (2025)