Approximation algorithms for minimum weight partial connected set cover problem

DOI10.1007/S10878-014-9782-5zbMATH Open1360.90224OpenAlexW2051063311MaRDI QIDQ5963645FDOQ5963645

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

Recommendations

• A simple approximation algorithm for minimum weight partial connected set cover
• An approximation algorithm for maximum weight budgeted connected set cover
• Using homogeneous weights for approximating the partial cover problem
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
• scientific article; zbMATH DE number 1305393

zbMATH Keywords

approximation algorithmgreedy algorithmset coversubmodular function

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity and approximation of the connected set-cover problem
• A simple approximation algorithm for minimum weight partial connected set cover

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963645)