A primal-dual approximation algorithm for generalized Steiner network problems
From MaRDI portal
Publication:5248542
DOI10.1145/167088.167268zbMath1310.90116OpenAlexW1985672402MaRDI QIDQ5248542
Vijay V. Vazirani, David P. Williamson, Milena Mihail, Michel X. Goemans
Publication date: 7 May 2015
Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/167088.167268
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items (9)
Approximating minimum-cost graph problems with spanning tree edges ⋮ Approximation Algorithms for a Network Design Problem ⋮ The parsimonious property of cut covering problems and its applications ⋮ Rounding algorithms for covering problems ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover ⋮ Linear bounds for on-line Steiner problems ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees ⋮ Network flow spanners ⋮ Eisenberg-Gale markets: algorithms and game-theoretic properties
This page was built for publication: A primal-dual approximation algorithm for generalized Steiner network problems
