Approximation Algorithms for the Set Covering and Vertex Cover Problems

Cited in

(only showing first 100 items - show all)

Efficient approximation of Min Set Cover by moderately exponential algorithms
Efficient bounds for the stable set, vertex cover and set packing problems
Equivalent approximation algorithms for node cover
A fast approximation algorithm for the multicovering problem
Pick-and-choose heuristics for partial set covering
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
Performance of a neural network method with set partitioning
A new fixed point approach for stable networks and stable marriages
The multicovering problem
A unified approximation algorithm for node-deletion problems
Simple Lagrangian heuristic for the set covering problem
Computational experience with approximation algorithms for the set covering problem
On dependent randomized rounding algorithms
Pareto optimality and a class of set covering heuristics
Clustering heuristics for set covering
Network flow and 2-satisfiability
A graph approximation heuristic for the vertex cover problem on planar graphs
A modified greedy heuristic for the set covering problem with improved worst case bound
On approximation algorithms for the minimum satisfiability problem
Semidefinite programming in combinatorial optimization
Rounding algorithms for covering problems
On the distribution of the domination number for random class cover catch digraphs
Fast stabbing of boxes in high dimensions
Approximating minimum feedback vertex sets in hypergraphs
Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
Multiple facility location on a network with linear reliability order of edges
O(f) bi-criteria approximation for capacitated covering with hard capacities
The relationship between attribute reducts in rough sets and minimal vertex covers of graphs
Reference points and approximation algorithms in multicriteria discrete optimization
The generalized vertex cover problem and some variations
Approximating the dense set-cover problem
Heuristic methods and applications: A categorized survey
A flexible formal framework for masking/demasking faults
Almost optimal set covers in finite VC-dimension
Improved approximation algorithms for minimum AND-circuits problem via \(k\)-set cover
Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
On approximation of the submodular set cover problem
Online budgeted maximum coverage
Relaxing the strong triadic closure problem for edge strength inference
Approximation algorithm for the partial set multi-cover problem
Approximation algorithm for the multicovering problem
Approximation algorithm for stochastic set cover problem
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
A primal-dual approximation algorithm for \textsc{minsat}
Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
Approximation of set multi-cover via hypergraph matching
Iterative partial rounding for vertex cover with hard capacities
An improved configuration checking-based algorithm for the unicost set covering problem
Restricted parameter range promise set cover problems are easy
A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
A primal-dual algorithm for the minimum partial set multi-cover problem
Efficient approximation algorithms for maximum coverage with group budget constraints
Capacitated domination: problem complexity and approximation algorithms
Approximation algorithms for clique transversals on some graph classes
Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
Linear kernels for separating a graph into components of bounded size
On parallelizing a greedy heuristic for finding small dominant sets
A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
Local ratio method on partial set multi-cover
Approximation of the quadratic set covering problem
Flip distance between triangulations of a planar point set is APX-hard
Experimental analysis of approximation algorithms for the vertex cover and set covering problems
The set covering problem revisited: an empirical study of the value of dual information
An improved approximation algorithm for vertex cover with hard capacities
Randomized approximation for the set multicover problem in hypergraphs
Minimum power partial multi-cover on a line
Optimal distributed covering algorithms
Online and approximate network construction from bounded connectivity constraints
Vertex cover meets scheduling
Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
Clustering on \(k\)-edge-colored graphs
Clustering through continuous facility location problems
On the Fractional Solution to the Set Covering Problem
A class of manpower scheduling problems
Geometric rounding: A dependent randomized rounding scheme
On dependent randomized rounding algorithms
Combinatorics for smaller kernels: the differential of a graph
A Tight Bound for Stochastic Submodular Cover
An articulation point-based approximation algorithm for minimum vertex cover problem
Autarkies and Persistencies for QUBO
Integrated Supply Chain Management via Randomized Rounding
The multi‐integer set cover and the facility terminal cover problem
A simple effective heuristic for embedded mixed-integer quadratic programming
Evaluation of monotone DNF formulas
Limits of local search: quality and efficiency
Capacitated domination problem
Capacitated Domination Problem
The Minimum Substring Cover Problem
New complexity results for the k-covers problem
Domination in Geometric Intersection Graphs
Minimum vertex cover in rectangle graphs
On point covers of c-oriented polygons
An approximation algorithm for the partial vertex cover problem in hypergraphs
Matheuristics: survey and synthesis
Linear‐time algorithms for eliminating claws in graphs
A parameterized approximation algorithm for the multiple allocation \(k\)-hub center

This page was built for publication: Approximation Algorithms for the Set Covering and Vertex Cover Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3947140)