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)

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

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)