Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search

DOI10.1007/11970125_23MaRDI QIDQ5443528zbMATH OpenOpenAlexFDO

Authors Asaf Levin

Publication date 21 February 2008

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11970125_23

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
• scientific article; zbMATH DE number 2081030
• Uniform unweighted set cover: the power of non-oblivious local search
• A modified greedy algorithm for dispersively weighted 3-set cover

Cited in

(22)

• A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
• A new approximation algorithm for k-set cover problem
• Approximation of the \(k\)-batch consolidation problem
• Greedy local improvement and weighted set packing approximation
• Boolean functions with long prime implicants
• A local search 4/3-approximation algorithm for the minimum 3-path partition problem
• A modified greedy algorithm for dispersively weighted 3-set cover
• The set cover problem with interval weights and the greedy algorithm for its solution
• A novel local search algorithm with configuration checking and scoring mechanism for the set k‐covering problem
• A GRASP algorithm to solve the unicost set covering problem
• Parameterized and Exact Computation
• An improved approximation algorithm for the minimum 3-path partition problem
• Uniform unweighted set cover: the power of non-oblivious local search
• Approximation and Online Algorithms
• Approximating activation edge-cover and facility location problems
• Set-cover approximation
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• scientific article; zbMATH DE number 7561664 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• scientific article; zbMATH DE number 2081030 (Why is no real title available?)

This page was built for publication: Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search

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