Approximation algorithms for minimum weight partial connected set cover problem

DOI10.1007/s10878-014-9782-5zbMath1360.90224OpenAlexW2051063311MaRDI QIDQ5963645

Xianliang Liu, Yao-Lin Jiang, Wei Wang, Dongyue Liang, Zhao Zhang

Publication date: 23 February 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-014-9782-5

zbMATH Keywords

approximation algorithmgreedy algorithmsubmodular functionset cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (1)

A simple approximation algorithm for minimum weight partial connected set cover

Cites Work

• Improved performance of the greedy algorithm for partial cover
• The relation of connected set cover and group Steiner tree
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximating Fault-Tolerant Group-Steiner problems
• A threshold of ln n for approximating set cover
• Saving an epsilon
• A Greedy Heuristic for the Set-Covering Problem
• Approximation algorithms for constrained for constrained node weighted steiner tree problems
• Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
• Connected Set Cover Problem and Its Applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation algorithms for minimum weight partial connected set cover problem