A Greedy Heuristic for the Set-Covering Problem
From MaRDI portal
Publication:3887227
DOI10.1287/moor.4.3.233zbMath0443.90066MaRDI 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 solution; binary matrix; set-covering problem; greedy heuristic; asymptotic exactness estimation
90C09: Boolean programming
Related Items
Computing near-optimal solutions for the dominating subset with minimal weight problem, APPROXIMATION ALGORITHM FOR MULTIPLE-TOOL MILLING, On the Greedy Heuristic for Continuous Covering and Packing Problems, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, Capacitated Domination Problem, The Minimum Substring Cover Problem, Approximation algorithms for the design of SDH/SONET networks, A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM, 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, On a minimum linear classification problem, Set covering approach for reconstruction of sibling relationships, On the primer selection problem in polymerase chain reaction experiments, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Minimum average routing path clustering problem in multi-hop 2-D underwater sensor networks, Learning the set covering machine by bound minimization and margin-sparsity trade-off, On approximation of the submodular set cover problem, Solving the feedback vertex set problem on undirected graphs, On the order of test goals in specification-based testing, 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), 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, Logical analysis of data -- the vision of Peter L. Hammer, On ring grooming in optical networks, Approximation of the quadratic set covering problem, Admission control with advance reservations in simple networks, Total energy optimal multicasting in wireless ad hoc networks, A goal programming approach to solve linear fractional multi-objective set covering problem., Maximum patterns in datasets, A modified greedy algorithm for dispersively weighted 3-set cover, Experimental analysis of approximation algorithms for the vertex cover and set covering problems, Algorithms of discrete optimization and their application to problems with fuzzy coefficients, Approximation algorithms for covering/packing integer programs, The minimum-entropy set cover problem, An improved approximation algorithm for vertex cover with hard capacities, Heuristic algorithms for siting alternative-fuel stations using the flow-refueling location model, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks, An ex-post bound on the greedy heuristic for the uncapacitated facility location problem, Primal-Dual Schema for Capacitated Covering Problems, Parameterized Learnability of k-Juntas and Related Problems, On the Approximability of Some Haplotyping Problems, On the Fractional Solution to the Set Covering Problem, Extensions of the Minimum Dominating Set Problem, Absolute bounds on optimal cost for a class of set covering problems, Heuristics for the fixed cost median problem, Worst case analysis of a class of set covering heuristics, A class of manpower scheduling problems, Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs, Exact Learning of Discretized Geometric Concepts, On the distribution of the domination number for random class cover catch digraphs, Traffic assignment in communication satellites, Preserving approximation in the min-weighted set cover problem, Randomized approximation of bounded multicovering problems, Constraint classification in mathematical programming, A critical review of discrete filled function methods in solving nonlinear discrete optimization problems, Approximation algorithms for scheduling unrelated parallel machines, On approximation problems related to the independent set and vertex cover problems, 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, Using a facility location algorithm to solve large set covering problems, Iterative Dutch combinatorial auctions, Beyond Moulin mechanisms, Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs, Dynamic shortest paths and transitive closure: algorithmic techniques and data structures, An effective and simple heuristic for the set covering problem, Optimal solutions to minimum total energy broadcasting problem in wireless ad hoc networks, Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms, New primal-dual algorithms for Steiner tree problems, Construction of \(\epsilon\)-nets, Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems, Mass customization of travel packages: Data mining approach, The minimum substring cover 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, Minimum partition of an independence system into independent sets, Solving multiple scenarios in a combinatorial auction, Path hitting in acyclic graphs, Approximating the traffic grooming problem, 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, The greedy algorithm for domination in graphs of maximum degree 3, 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, Mining Pareto-optimal modules for delayed product differentiation, Efficient bounds for the stable set, vertex cover and set packing problems, Equivalent approximation algorithms for node cover, Optimal attribute sets for identifications and diagnoses, Conditional covering: greedy heuristics and computational results, Entropy and set covering, Hierarchical approach to the process planning problem, Solving large set covering problems on a personal computer, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework, A probabilistic heuristic for a computationally difficult set covering problem, Pick-and-choose heuristics for partial set covering, Conditional clusters, musters, and probability, Approximation algorithms for hitting objects with straight lines, Analysis of a greedy heuristic for finding small dominating sets in graphs, Complexity of the repeaters allocating problem, Parallel and serial heuristics for the minimum set cover problem, Learning in parallel, Processor optimization for flow graphs, The multicovering problem, 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, A Lagrangian-based heuristic for large-scale set covering problems, Approximating the weight of shallow Steiner trees, On dependent randomized rounding algorithms, 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, 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, Optimization by ghost image processes in neural networks, A theory for memory-based learning, Approximability of maximum splitting of k-sets and some other Apx-complete problems, Solving large set covering problems for crew scheduling, Finding the minimum weight IIS cover of an infeasible system of linear inequalities, Rounding algorithms for covering problems, The design of a 0-1 integer optimizer and its application in the Carmen system, Negotiation and cooperation in multi-agent environments, Approximating covering integer programs with multiplicity constraints, Hereditary systems and greedy-type algorithms., Two sensitivity theorems in fuzzy integer programming., A neural network for the minimum set covering problem, Fast stabbing of boxes in high dimensions, Generalized submodular cover problems and applications, A mixed-mode BIST scheme based on folding compression, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, On approximation of the vertex cover problem in hypergraphs, Heuristic methods and applications: A categorized survey, An analysis of the greedy algorithm for the submodular set covering problem, Algorithms for multicast connection under multi-path routing model., Stock selection heuristics for interdependent items, A fuzzy genetic algorithm for driver scheduling, Scheduling of conditional executed jobs on unrelated processors, An algorithm for large scale 0-1 integer programming with application to airline crew scheduling, Almost optimal set covers in finite VC-dimension
