On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique

DOI10.1137/050625382zbMath1096.68164OpenAlexW3023912806MaRDI QIDQ5470793

Dror Rawitz, Reuven Bar Yehuda

Publication date: 1 June 2006

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmsprimal-dualcovering problemslocal ratio

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (16)

Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique ⋮ Generalized Hypergraph Matching via Iterated Packing and Local Ratio ⋮ A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems ⋮ Using fractional primal-dual to schedule split intervals with demands ⋮ Partial multicovering and the \(d\)-consecutive ones property ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ Distributed approximation of cellular coverage ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Admission control with advance reservations in simple networks ⋮ Elementary approximation algorithms for prize collecting Steiner tree problems ⋮ Kernels for packing and covering problems ⋮ The set covering problem revisited: an empirical study of the value of dual information ⋮ Distributed set cover approximation: Primal-dual with optimal locality ⋮ Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems ⋮ A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

This page was built for publication: On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique