A Greedy Heuristic for the Set-Covering Problem
From MaRDI portal
Publication:3887227
DOI10.1287/MOOR.4.3.233zbMath0443.90066OpenAlexW2157054705MaRDI QIDQ3887227
No author found.
Publication date: 1979
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.4.3.233
approximate solutionbinary matrixset-covering problemgreedy heuristicasymptotic exactness estimation
Related Items (only showing first 100 items - show all)
Task scheduling in networks ⋮ Parallel and sequential approximation of shortest superstrings ⋮ ON THE DISCRETE UNIT DISK COVER PROBLEM ⋮ A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems ⋮ On dependent randomized rounding algorithms ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ Resource allocation problem under single resource assignment ⋮ A generalized model and a heuristic algorithm for the large-scale covering tour problem ⋮ A class of manpower scheduling problems ⋮ Network Inspection for Detecting Strategic Attacks ⋮ Partial Resampling to Approximate Covering Integer Programs ⋮ Approximation algorithms for a genetic diagnostics problem ⋮ Approximability results for the $p$-centdian and the converse centdian problems ⋮ Set covering heuristics in a benders decomposition for railway timetabling ⋮ An Exact Method for the Minimum Feedback Arc Set Problem ⋮ A hybrid heuristic approach to minimize number of tardy jobs in group technology systems ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Set selection under explorable stochastic uncertainty via covering techniques ⋮ Minimum k‐cores and the k‐core polytope ⋮ Unique response Roman domination: complexity and algorithms ⋮ Ising Machines for Diophantine Problems in Physics ⋮ Technical Note—Online Hypergraph Matching with Delays ⋮ Approximation algorithms for feasible cut and multicut problems ⋮ Spatial state-action features for general games ⋮ Real-time passenger bus routing problems with preferences and tradeoffs ⋮ Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems ⋮ Feasible rounding based diving strategies in branch-and-bound methods for mixed-integer optimization ⋮ Clustering in Hypergraphs to Minimize Average Edge Service Time ⋮ Efficient heuristics for a partial set covering problem with mutually exclusive pairs of facilities ⋮ Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback ⋮ The Impact of a New Formulation When Solving the Set Covering Problem Using the ACO Metaheuristic ⋮ A binary monkey search algorithm variation for solving the set covering problem ⋮ Monochromatic partitioning of colored points by lines ⋮ An optimization method for characterizing two groups of data ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Improved Algorithm for Resource Allocation Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Combining metaheuristics with mathematical programming, constraint programming and machine learning ⋮ An efficient distributed algorithm for constructing small dominating sets ⋮ Capacitated Domination Problem ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Coresets for the Nearest-Neighbor Rule ⋮ Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ Absolute bounds on optimal cost for a class of set covering problems ⋮ Unnamed Item ⋮ Combining metaheuristics with mathematical programming, constraint programming and machine learning ⋮ Computing near-optimal solutions for the dominating subset with minimal weight problem ⋮ Model-Based Testing ⋮ On point covers of \(c-\)oriented polygons ⋮ Combinatorial optimization algorithms for radio network planning ⋮ Flight graph based genetic algorithm for crew scheduling in airlines ⋮ Enumeration technique for set covering problems: a combinatorial approach ⋮ A genetic algorithm for public transport driver scheduling ⋮ Discovering unbounded unions of regular pattern languages from positive examples ⋮ APPROXIMATION ALGORITHM FOR MULTIPLE-TOOL MILLING ⋮ On a minimum linear classification problem ⋮ Unnamed Item ⋮ Set covering approach for reconstruction of sibling relationships ⋮ Dynamic \(((1+\epsilon)\ln n)\)-approximation algorithms for minimum set cover and dominating set ⋮ Unnamed Item ⋮ The Minimum Substring Cover Problem ⋮ Iterative Column Generation Algorithm for Generalized Multi-Vehicle Covering Tour Problem ⋮ On the primer selection problem in polymerase chain reaction experiments ⋮ Approximation algorithms for minimum weight partial connected set cover problem ⋮ An approximation algorithm for the partial vertex cover problem in hypergraphs ⋮ Constant-time distributed dominating set approximation ⋮ The strong domination problem in block graphs and proper interval graphs ⋮ On Geometric Set Cover for Orthants ⋮ On Multiple Coverings of Fixed Size Containers with Non-Euclidean Metric by Circles of Two Types ⋮ Hardness of approximate two-level logic minimization and PAC learning with membership queries ⋮ Approximation algorithms for the design of SDH/SONET networks ⋮ Approximating Distance Measures for the Skyline ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ Approximation algorithms in combinatorial scientific computing ⋮ A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM ⋮ Efficient Online Linear Optimization with Approximation Algorithms ⋮ Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs ⋮ Exact Learning of Discretized Geometric Concepts ⋮ Distributed Spanner Approximation ⋮ Heuristics for the fixed cost median problem ⋮ Dynamic data structures for fat objects and their applications ⋮ On the Greedy Heuristic for Continuous Covering and Packing Problems ⋮ Unnamed Item ⋮ A distributed algorithm for a set cover game ⋮ Worst case analysis of a class of set covering heuristics ⋮ Equivalent approximation algorithms for node cover ⋮ A-priori upper bounds for the set covering problem ⋮ On pseudo-disk hypergraphs ⋮ Improved performance of the greedy algorithm for partial cover ⋮ Improved solutions to the Steiner triple covering problem ⋮ Beyond Moulin mechanisms ⋮ Give-and-take based peer-to-peer content distribution networks ⋮ Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs ⋮ The submodular joint replenishment problem ⋮ Multi-start iterated tabu search for the minimum weight vertex cover problem ⋮ An efficient local search heuristic with row weighting for the unicost set covering problem ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
This page was built for publication: A Greedy Heuristic for the Set-Covering Problem
