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
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, APPROXIMATION ALGORITHM FOR MULTIPLE-TOOL MILLING, On a minimum linear classification problem, Unnamed Item, Set covering approach for reconstruction of sibling relationships, 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, A mixed-mode BIST scheme based on folding compression, An approximation algorithm for the license and shift class design problem, An experimental comparison of three heuristics for the WVCP, A modified greedy heuristic for the set covering problem with improved worst case bound, Learning Boolean concepts in the presence of many irrelevant features, Theoretical complexity of grid cover problems used in radar applications, Optimal attribute sets for identifications and diagnoses, Optimization by ghost image processes in neural networks, A theory for memory-based learning, Conditional covering: greedy heuristics and computational results, Tweakable block ciphers secure beyond the birthday bound in the ideal cipher model, Entropy and set covering, A new approximation algorithm for \(k\)-set cover problem, Hierarchical approach to the process planning problem, Solving large set covering problems on a personal computer, Approximability of maximum splitting of k-sets and some other Apx-complete problems, Scheduling of conditional executed jobs on unrelated processors, An algorithm for large scale 0-1 integer programming with application to airline crew scheduling, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework, Carousel greedy: a generalized greedy algorithm with applications in optimization, Almost optimal set covers in finite VC-dimension, Solving large set covering problems for crew scheduling, A probabilistic heuristic for a computationally difficult set covering problem, Pick-and-choose heuristics for partial set covering, Finding the minimum weight IIS cover of an infeasible system of linear inequalities, Rounding algorithms for covering problems, Calculating approximation guarantees for partial set cover of pairs, The \(k\)-hop connected dominating set problem: approximation and hardness, A simple approximation algorithm for minimum weight partial connected set cover, FPT approximation schemes for maximizing submodular functions, Min-energy broadcast in mobile ad hoc networks with restricted motion, Enumeration technique for solving multi-objective quadratic set-covering problem using goal programming, The design of a 0-1 integer optimizer and its application in the Carmen system, Negotiation and cooperation in multi-agent environments, Strengthening hash families and compressive sensing, Overcoming controllability problems in distributed testing from an input output transition system, New pairwise spanners, Approximating covering integer programs with multiplicity constraints, Maximum subset intersection, Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost, Hereditary systems and greedy-type algorithms., Homomorphic secret sharing for low degree polynomials, A heuristic algorithm for finding cost-effective solutions to real-world school bus routing problems, Minimum average routing path clustering problem in multi-hop 2-D underwater sensor networks, Two sensitivity theorems in fuzzy integer programming., Learning the set covering machine by bound minimization and margin-sparsity trade-off, Energy efficient low-cost virtual backbone construction for optimal routing in wireless sensor networks, Conditional clusters, musters, and probability, Approximation algorithms for hitting objects with straight lines, On approximation of the submodular set cover problem, \((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity, A tolerance function for the multiobjective set covering problem, Designing cost-sharing methods for Bayesian games, Solving the feedback vertex set problem on undirected graphs, Analysis of a greedy heuristic for finding small dominating sets in graphs, Complexity of the repeaters allocating problem, Online budgeted maximum coverage, Parallel and serial heuristics for the minimum set cover problem, Learning in parallel, Online dominating set, A set-cover-based approach for the test-cost-sensitive attribute reduction problem, Covering arrays via set covers, Geometric hitting set for segments of few orientations, The relationship between attribute reducts in rough sets and minimal vertex covers of graphs, Towards flexible demands in online leasing problems, Covering problems in edge- and node-weighted graphs, An optimization model for freight transport using urban rail transit, Processor optimization for flow graphs, The multicovering problem, Approximation algorithm for the partial set multi-cover problem, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, On approximation of the vertex cover problem in hypergraphs, Approximation algorithm for the multicovering problem, Spherical classification of data, a new rule-based learning method, Lift-and-project methods for set cover and knapsack, Offline and online facility leasing, Efficient feature selection for logical analysis of large-scale multi-class datasets, Approximate CVP\(_p\) in time \(2^{0.802n}\), A unified approximation algorithm for node-deletion problems, Methods for task allocation via agent coalition formation, Differential approximation algorithms for some combinatorial optimization problems, Simple Lagrangian heuristic for the set covering problem, Computational experience with approximation algorithms for the set covering problem, Heuristic methods and applications: A categorized survey, Reflections on kernelizing and computing unrooted agreement forests, A Lagrangian-based heuristic for large-scale set covering problems, A neural network for the minimum set covering problem, An analysis of the greedy algorithm for the submodular set covering problem, Approximating the weight of shallow Steiner trees, Fast stabbing of boxes in high dimensions, Generalized submodular cover problems and applications, On dependent randomized rounding algorithms, Algorithms for multicast connection under multi-path routing model., Algorithms for large scale set covering problems, Pareto optimality and a class of set covering heuristics, A heuristic algorithm for the multi-criteria set-covering problems, A set covering reformulation of the pure fixed charge transportation problem, The maximum clique problem, Stock selection heuristics for interdependent items, A fuzzy genetic algorithm for driver scheduling, Siting renewable power generation assets with combinatorial optimisation, Approximation of the Clustered Set Covering Problem, On the complexity of minimum \(q\)-domination partization problems, On parallelizing a greedy heuristic for finding small dominant sets, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Small Stretch Pairwise Spanners and Approximate $D$-Preservers, How to split the costs and charge the travellers sharing a ride? Aligning system's optimum with users' equilibrium, Construction of component tapes for radial placement machines, Two-phase method and Lagrangian relaxation to solve the bi-objective set covering problem, Approximability of identifying codes and locating-dominating codes, Exact learning from an honest teacher that answers membership queries, Minimum Dominating Set Problem for Unit Disks Revisited, Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers, Design of a heuristic algorithm for the generalized multi-objective set covering problem, Logical analysis of data -- the vision of Peter L. Hammer, On ring grooming in optical networks, Hypergraph representation via axis-aligned point-subspace cover, Discrete dynamical system approaches for Boolean polynomial optimization, Heuristic algorithms for siting alternative-fuel stations using the flow-refueling location model, A PTAS for the horizontal rectangle stabbing problem, A polynomial-time approximation to a minimum dominating set in a graph, Approximating activation edge-cover and facility location problems, The network-untangling problem: from interactions to activity timelines, Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem, Local ratio method on partial set multi-cover, Randomized Online Algorithms for Set Cover Leasing Problems, A Practical Greedy Approximation for the Directed Steiner Tree Problem, The minimum cost network upgrade problem with maximum robustness to multiple node failures, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, Approximation algorithm for the stochastic prize-collecting set multicover problem, Approximation algorithms for the minimum power cover problem with submodular/linear penalties, Primal-Dual Schema for Capacitated Covering Problems, Approximation of the quadratic set covering problem, Towards faster local search for minimum weight vertex cover on massive graphs, Algorithm and hardness results on neighborhood total domination in graphs, Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), Approximating minimum cost source location problems with local vertex-connectivity demands, Parameterized Learnability of k-Juntas and Related Problems, On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs, Learning bounds via sample width for classifiers on finite metric spaces, How to guard a graph against tree moves, Bounded max-colorings of graphs, A graph approach for fuzzy-rough feature selection, Feedback robustness in structured closed-loop system, Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis, On the complexity of constructing minimum changeover cost arborescences, On the complexity of the selective graph coloring problem in some special classes of graphs, Admission control with advance reservations in simple networks, Set Covering with Ordered Replacement: Additive and Multiplicative Gaps, An improved configuration checking-based algorithm for the unicost set covering problem, Total energy optimal multicasting in wireless ad hoc networks, Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands, Reoptimization of set covering problems, A goal programming approach to solve linear fractional multi-objective set covering problem., Maximum patterns in datasets, Functional dependencies are helpful for partial materialization of data cubes, Restricted parameter range promise set cover problems are easy, A modified greedy algorithm for dispersively weighted 3-set cover, On the order of test goals in specification-based testing, Experimental analysis of approximation algorithms for the vertex cover and set covering problems, A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation, Approximating constrained minimum cost input-output selection for generic arbitrary pole placement in structured systems, A fast beam orientation optimization method that enforces geometric constraints in IMRT for total marrow irradiation, An efficient local search framework for the minimum weighted vertex cover problem, A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem, On the Complexity Landscape of the Domination Chain, Algorithms of discrete optimization and their application to problems with fuzzy coefficients, Sparsity in max-plus algebra and systems, The set covering problem revisited: an empirical study of the value of dual information, Empirical study of the greedy heuristic as applied to the link selection problem, Level-aware collective spatial keyword queries, Algorithmic results on double Roman domination in graphs, An approximation algorithm for vehicle routing with compatibility constraints, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, On the Discrete Unit Disk Cover Problem, Designing Cost-Sharing Methods for Bayesian Games, A primal-dual algorithm for the minimum partial set multi-cover problem, On the Approximability of Some Haplotyping Problems, Solving the non-unicost set covering problem by using cuckoo search and black hole optimization, Enhancing the elicitation of diverse decision objectives for public planning, Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks, The power of the weighted sum scalarization for approximating multiobjective optimization problems, An ex-post bound on the greedy heuristic for the uncapacitated facility location problem, A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem, A primal-dual algorithm for the minimum power partial cover problem, Problems and algorithms for covering arrays via set covers, On the Fractional Solution to the Set Covering Problem, Extensions of the Minimum Dominating Set Problem, Algorithm and hardness results on hop domination in graphs, Approximation algorithms for covering/packing integer programs, An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries, The minimum-entropy set cover problem, An improved approximation algorithm for vertex cover with hard capacities, Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks, A set covering approach for multi-depot train driver scheduling, A probabilistic approach to case-based inference, Mining circuit lower bound proofs for meta-algorithms, Order picking optimization with rack-moving mobile robots and multiple workstations, Tight bounds on subexponential time approximation of set cover and related problems, The aircraft maintenance base location problem, 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, An effective and simple heuristic for the set covering problem, Deterministic versus randomized adaptive test cover, Hybrid column generation for large-size covering integer programs: application to transportation planning, A hybrid Lagrangean heuristic with GRASP and path-relinking for set \(k\)-covering, A Pareto-metaheuristic for a bi-objective winner determination problem in a combinatorial reverse auction, A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints, Optimal solutions to minimum total energy broadcasting problem in wireless ad hoc networks, Refined algorithms for hitting many intervals, Towards the price of leasing online, A practical greedy approximation for the directed Steiner tree problem, Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms, New primal-dual algorithms for Steiner tree problems, On the union of intermediate nodes of shortest paths, Traffic assignment in communication satellites, Cost sharing and strategyproof mechanisms for set cover games, Black-box Trace\&Revoke codes, A variable neighborhood search algorithm for the multimode set covering problem, Static and dynamic source locations in undirected networks, A formal logic approach to constrained combinatorial testing, Summarizing transactional databases with overlapped hyperrectangles, An auxiliary function method for global minimization in integer programming, Complexity of majority monopoly and signed domination problems, On the approximation ability of evolutionary optimization with application to minimum set cover, On the approximability of covering points by lines and related problems, Uniform unweighted set cover: the power of non-oblivious local search, On the complexity of calculating sensitivity parameters in Boolean programming problems, Vector bin packing with multiple-choice, Improved approximation for guarding simple galleries from the perimeter, The relation of connected set cover and group Steiner tree, Construction of \(\epsilon\)-nets, Complexity and approximation of the connected set-cover problem, Attribute reduction of data with error ranges and test costs, A survey on the structure of approximation classes, Tighter approximation bounds for minimum CDS in unit disk graphs, Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems, On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems, Textual data compression in computational biology: algorithmic techniques, Approximation schemes for deal splitting and covering integer programs with multiplicity constraints, Bounding the payment of approximate truthful mechanisms, Distributed algorithms for covering, packing and maximum weighted matching, A note on the clustered set covering problem, Preserving approximation in the min-weighted set cover problem, Randomized approximation of bounded multicovering problems, Mass customization of travel packages: Data mining approach, Evaluation of monotone DNF formulas, The minimum substring cover problem, Constraint classification in mathematical programming, The within-strip discrete unit disk cover problem, On the complexity of the regenerator cost problem in general networks with traffic grooming, Capacitated domination problem, Approximation algorithms for art gallery problems in polygons, Approximate shortest paths guided by a small index, Surrogate constraint normalization for the set covering problem, A critical review of discrete filled function methods in solving nonlinear discrete optimization problems, Hyperbolic set covering problems with competing ground-set elements, Covering compact metric spaces greedily, A set covering based approach to find the reduct of variable precision rough set, Hitting sets online and unique-MAX coloring, On the distribution of the domination number for random class cover catch digraphs, A randomised approximation algorithm for the hitting set problem, Minimum partition of an independence system into independent sets, Primal-dual schema for capacitated covering problems, Solving multiple scenarios in a combinatorial auction, Path hitting in acyclic graphs, Approximating the traffic grooming problem, Approximation algorithms for scheduling unrelated parallel machines, Efficient approximation of Min Set Cover by moderately exponential algorithms, An application of the greedy heuristic of set cover to traffic checks, Independent sets in bounded-degree hypergraphs, On approximation problems related to the independent set and vertex cover problems, The greedy algorithm for domination in graphs of maximum degree 3, On two restricted ancestors tree problems, Weighted sum coloring in batch scheduling of conflicting jobs, Parameterized learnability of juntas, Covering the edges of bipartite graphs using \(K_{2,2}\) graphs, Mechanism design for set cover games with selfish element agents, Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis, An order-based algorithm for minimum dominating set with application in graph mining, Mining Pareto-optimal modules for delayed product differentiation, Classification using proximity catch digraphs, Exploring further advantages in an alternative formulation for the set covering problem, Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem, Optimal control of greenhouse climate: methodology, Efficient bounds for the stable set, vertex cover and set packing problems, Using a facility location algorithm to solve large set covering problems, Iterative Dutch combinatorial auctions, When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem, Randomized approximation for the set multicover problem in hypergraphs
