Approximation Algorithms for the Set Covering and Vertex Cover Problems
From MaRDI portal
Publication:3947140
DOI10.1137/0211045zbMath0486.68067OpenAlexW2088188524MaRDI QIDQ3947140
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211045
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Discrete mathematics in relation to computer science (68R99)
Related Items
Equivalent approximation algorithms for node cover, Vertex cover meets scheduling, A graph approximation heuristic for the vertex cover problem on planar graphs, Linear kernels for separating a graph into components of bounded size, Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, A fast approximation algorithm for the multicovering problem, A modified greedy heuristic for the set covering problem with improved worst case bound, On parallelizing a greedy heuristic for finding small dominant sets, An edge-reduction algorithm for the vertex cover problem, On approximation algorithms for the minimum satisfiability problem, A packet filter placement problem with application to defense against spoofed denial of service attacks, Clustering on \(k\)-edge-colored graphs, Almost optimal set covers in finite VC-dimension, On a generalization of Nemhauser and Trotter's local optimization theorem, A primal-dual approximation algorithm for partial vertex cover: Making educated guesses, Partial multicuts in trees, Semidefinite programming in combinatorial optimization, Clustering through continuous facility location problems, A primal-dual approximation algorithm for \textsc{minsat}, Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms, Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem, Minimum power partial multi-cover on a line, Pick-and-choose heuristics for partial set covering, Rounding algorithms for covering problems, Local ratio method on partial set multi-cover, Multiple facility location on a network with linear reliability order of edges, Finding small stabilizers for unstable graphs, Geometric rounding: A dependent randomized rounding scheme, Approximation of the quadratic set covering problem, Improved approximation algorithms for minimum AND-circuits problem via \(k\)-set cover, Optimal distributed covering algorithms, Approximability of sparse integer programs, Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost, Approximation of set multi-cover via hypergraph matching, Flip distance between triangulations of a planar point set is APX-hard, Approximation algorithms for hitting objects with straight lines, A generalization of Nemhauser and Trotter's local optimization theorem, Iterative partial rounding for vertex cover with hard capacities, On approximation of the submodular set cover problem, Combinatorics for smaller kernels: the differential of a graph, Distributed algorithms for covering, packing and maximum weighted matching, Analysis of a greedy heuristic for finding small dominating sets in graphs, Complexity of the repeaters allocating problem, Online budgeted maximum coverage, Rounding to an integral program, A simple LP-free approximation algorithm for the minimum weight vertex cover problem, \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities, Preserving approximation in the min-weighted set cover problem, An improved configuration checking-based algorithm for the unicost set covering problem, Relaxing the strong triadic closure problem for edge strength inference, Randomized approximation of bounded multicovering problems, The relationship between attribute reducts in rough sets and minimal vertex covers of graphs, Evaluation of monotone DNF formulas, Reference points and approximation algorithms in multicriteria discrete optimization, Performance of a neural network method with set partitioning, The minimum substring cover problem, A new fixed point approach for stable networks and stable marriages, Approximating the tree and tour covers of a graph, The generalized vertex cover problem and some variations, Limits of local search: quality and efficiency, The multicovering problem, Capacitated domination problem, Restricted parameter range promise set cover problems are easy, Approximating the dense set-cover problem, New complexity results for the \(k\)-covers problem, Approximation algorithm for the partial set multi-cover problem, Minimum vertex cover in rectangle graphs, Surrogate constraint normalization for the set covering problem, Experimental analysis of approximation algorithms for the vertex cover and set covering problems, Approximation algorithm for the multicovering problem, A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem, The set covering problem revisited: an empirical study of the value of dual information, Approximation algorithm for stochastic set cover problem, On the distribution of the domination number for random class cover catch digraphs, A randomised approximation algorithm for the hitting set problem, Efficient approximation of Min Set Cover by moderately exponential algorithms, A primal-dual algorithm for the minimum partial set multi-cover problem, A unified approximation algorithm for node-deletion problems, On approximation problems related to the independent set and vertex cover 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, Efficient approximation algorithms for maximum coverage with group budget constraints, A flexible formal framework for masking/demasking faults, A simple rounding scheme for multistage optimization, A primal-dual algorithm for the minimum power partial cover problem, Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty, Fast stabbing of boxes in high dimensions, Approximating minimum feedback vertex sets in hypergraphs, Efficient bounds for the stable set, vertex cover and set packing problems, On dependent randomized rounding algorithms, An improved approximation algorithm for vertex cover with hard capacities, Pareto optimality and a class of set covering heuristics, Clustering heuristics for set covering, Capacitated domination: problem complexity and approximation algorithms, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, Approximation algorithms for clique transversals on some graph classes, Network flow and 2-satisfiability, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties, Randomized approximation for the set multicover problem in hypergraphs, An Articulation Point-Based Approximation Algorithm for Minimum Vertex Cover Problem, Autarkies and Persistencies for QUBO, On dependent randomized rounding algorithms, A class of manpower scheduling problems, Matheuristics: survey and synthesis, Linear‐time algorithms for eliminating claws in graphs, A parameterized approximation algorithm for the multiple allocation \(k\)-hub center, Computing connected-\(k\)-subgraph cover with connectivity requirement, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Online and Approximate Network Construction from Bounded Connectivity Constraints, Timeline cover in temporal graphs: exact and approximation algorithms, Online and approximate network construction from bounded connectivity constraints, Integrated Supply Chain Management via Randomized Rounding, Capacitated Domination Problem, On point covers of \(c-\)oriented polygons, The multi‐integer set cover and the facility terminal cover problem, The Minimum Substring Cover Problem, An approximation algorithm for the partial vertex cover problem in hypergraphs, A simple effective heuristic for embedded mixed-integer quadratic programming, Domination in Geometric Intersection Graphs, On the Fractional Solution to the Set Covering Problem, A Tight Bound for Stochastic Submodular Cover
