Primal-dual meets local search
From MaRDI portal
Publication:3581300
DOI10.1145/780542.780600zbMath1192.90232OpenAlexW2159115597MaRDI QIDQ3581300
Publication date: 16 August 2010
Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/780542.780600
Programming involving graphs or networks (90C35) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (8)
A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs ⋮ Chain-constrained spanning trees ⋮ Refuting a conjecture of goemans on bounded degree spanning trees ⋮ Approximation algorithms for finding low-degree subgraphs ⋮ Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems ⋮ A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids ⋮ Unnamed Item
This page was built for publication: Primal-dual meets local search
