Better Approximations for Tree Sparsity in Nearly-Linear Time

DOI10.1137/1.9781611974782.145zbMath1410.68394OpenAlexW4235809492MaRDI QIDQ4575893

Artūrs Bačkurs, Ludwig Schmidt, Piotr Indyk

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.145

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (6)

Bisection of bounded treewidth graphs by convolutions ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ On Integer Programming and Convolution.

This page was built for publication: Better Approximations for Tree Sparsity in Nearly-Linear Time