A modified greedy algorithm for dispersively weighted 3-set cover

DOI10.1016/J.DAM.2005.06.013MaRDI QIDQ2492216zbMATH OpenOpenAlexFDO

Authors Toshihiro Fujito, Tsuyoshi Okumura

Publication date 9 June 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.06.013

zbMATH Keywords

approximation algorithmsgreedy algorithmprimal-dual methodset cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 2081030
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
• Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• A Tight Analysis of the Greedy Algorithm for Set Cover

Cites work

• A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
• A Greedy Heuristic for the Set-Covering Problem
• A modified greedy heuristic for the set covering problem with improved worst case bound
• A threshold of ln n for approximating set cover
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Approximating k-set cover and complementary graph coloring
• Approximation algorithms for combinatorial problems
• Greedy local improvement and weighted set packing approximation
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 2081030 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• scientific article; zbMATH DE number 3220175 (Why is no real title available?)
• scientific article; zbMATH DE number 3232667 (Why is no real title available?)
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• On local search for weighted \(k\)-set packing
• On the ratio of optimal integral and fractional covers
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Optimization, approximation, and complexity classes
• Paths, Trees, and Flowers

Cited in

(3)

• A 6/5-approximation algorithm for the maximum 3-cover problem
• scientific article; zbMATH DE number 2081030 (Why is no real title available?)
• Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search

This page was built for publication: A modified greedy algorithm for dispersively weighted 3-set cover

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