Cover Image

A Strong Linear Programming Relaxation for Weighted Tree Augmentation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cohen-Addad, Vincent, Drygala, Marina, Klein, Nathan, Svensson, Ola
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Retriever Portfolios: A Principled Approach to Adaptive RAG
by: Stouras, Miltiadis, et al.
Published: (2026)

Data-Driven Solution Portfolios
by: Drygala, Marina, et al.
Published: (2024)

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

Scalable Private Partition Selection via Adaptive Weighting
by: Chen, Justin Y., et al.
Published: (2025)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
by: Cohen-Addad, Vincent, et al.
Published: (2022)

Distributed Algorithms for Euclidean Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Correlation Clustering Beyond the Pivot Algorithm
by: Behnezhad, Soheil, et al.
Published: (2024)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

Understanding the Cluster LP for Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Fair Clustering in the Sliding Window Model
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Dynamic Correlation Clustering in Sublinear Update Time
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

An Improved Greedy Approximation for (Metric) $k$-Means
by: Charikar, Moses, et al.
Published: (2026)

Combinatorial Correlation Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

Online Edge Coloring: Sharp Thresholds
by: Blikstad, Joakim, et al.
Published: (2025)

Deterministic Online Bipartite Edge Coloring
by: Blikstad, Joakim, et al.
Published: (2024)

Online Edge Coloring is (Nearly) as Easy as Offline
by: Blikstad, Joakim, et al.
Published: (2024)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
by: Anand, Aditya, et al.
Published: (2025)

Ghost Value Augmentation for $k$-Edge-Connectivity
by: Hershkowitz, D Ellis, et al.
Published: (2023)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
by: Bakshi, Ainesh, et al.
Published: (2023)

Thin Trees for Near Minimum Cuts
by: Klein, Nathan, et al.
Published: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

A Scalable Algorithm for Individually Fair K-means Clustering
by: Bateni, MohammadHossein, et al.
Published: (2024)

Dual Charging for Half-Integral TSP
by: Klein, Nathan, et al.
Published: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Solving the Correlation Cluster LP in Sublinear Time
by: Cao, Nairen, et al.
Published: (2025)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

A Randomized Rounding Approach for DAG Edge Deletion
by: Kalantarzadeh, Sina, et al.
Published: (2025)

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

Engineering Weighted Connectivity Augmentation Algorithms
by: Faraj, Marcelo Fonseca, et al.
Published: (2024)

Balancing Weights, Directed Sparsification, and Augmenting Paths
by: Li, Jason
Published: (2026)

Combinatorial Optimization using Comparison Oracles
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
by: Axiotis, Kyriakos, et al.
Published: (2024)