Computational experience with approximation algorithms for the set covering problem

DOI10.1016/S0377-2217(96)00161-0zbMath0929.90072OpenAlexW2064209160MaRDI QIDQ1278941

Tal Grossman, Avishai Wool

Publication date: 28 February 1999

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(96)00161-0

zbMATH Keywords

neural networkNP-hardset coveringrandomized greedy algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Siting renewable power generation assets with combinatorial optimisation ⋮ A-priori upper bounds for the set covering problem ⋮ Efficient Design of Compact Unstructured RNA Libraries Covering All k-mers ⋮ An efficient local search heuristic with row weighting for the unicost set covering problem ⋮ An effective and simple heuristic for the set covering problem ⋮ Solving a bicriteria problem of optimal service centers location ⋮ A theoretical justification of the set covering greedy heuristic of Caprara et al. ⋮ A GRASP algorithm to solve the unicost set covering problem ⋮ On a linearization technique for solving the quadratic set covering problem and variations ⋮ Fractional Set Cover in the Streaming Model. ⋮ A relax-and-cut algorithm for the set partitioning problem ⋮ An improved configuration checking-based algorithm for the unicost set covering problem ⋮ Randomized approximation of bounded multicovering problems ⋮ Optimal RSUs placement with delay bounded message dissemination in vehicular networks ⋮ Surrogate constraint normalization for the set covering problem ⋮ An efficient mean field approach to the set covering problem ⋮ Experimental analysis of approximation algorithms for the vertex cover and set covering problems ⋮ Building a large location table to find replicas of physics objects ⋮ Set covering approach for reconstruction of sibling relationships ⋮ The set covering problem revisited: an empirical study of the value of dual information ⋮ Model-based view planning ⋮ A new approach for solving set covering problem using jumping particle swarm optimization method ⋮ Computational experience with approximation algorithms for the set covering problem ⋮ An adaptive heuristic algorithm for VLSI test vectors selection ⋮ Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems ⋮ Column generation extensions of set covering greedy heuristics

Uses Software

• LOQO
• OR-Library

Cites Work

• Randomized approximation of bounded multicovering problems
• Probabilistic solution of the Dirichlet problem for biharmonic functions in discrete space
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• A genetic algorithm for the set covering problem
• Computational experience with approximation algorithms for the set covering problem
• An algorithm for set covering problem
• An algorithm for large scale 0-1 integer programming with application to airline crew scheduling
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• On the maximum number of edges in a c₄‐free subgraph of q_n
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item