A linear-time approximation algorithm for the weighted vertex cover problem
From MaRDI portal
Cited in
(only showing first 100 items - show all)- Equivalent approximation algorithms for node cover
- A fast approximation algorithm for the multicovering problem
- Approximation algorithms for hitting objects with straight lines
- Complexity of the repeaters allocating problem
- A bounded approximation for the minimum cost 2-sat problem
- A new fixed point approach for stable networks and stable marriages
- 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
- An experimental comparison of three heuristics for the WVCP
- Rounding algorithms for covering problems
- On residual approximation in solution extension problems
- Dynamic algorithms via the primal-dual method
- Efficient algorithm for the vertex cover \(P_k\) problem on cacti
- O(f) bi-criteria approximation for capacitated covering with hard capacities
- Approximating the dense set-cover problem
- A factor 2 approximation algorithm for the vertex cover P₃ problem
- Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
- Online budgeted maximum coverage
- Approximation algorithm for stochastic set cover problem
- The power of the weighted sum scalarization for approximating multiobjective optimization problems
- A reduction tree approach for the discrete time/cost trade-off problem
- A primal-dual approximation algorithm for \textsc{minsat}
- Iterative partial rounding for vertex cover with hard capacities
- Efficient approximation algorithms for maximum coverage with group budget constraints
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- A general approximation method for bicriteria minimization problems
- Approximation of the quadratic set covering problem
- The vertex cover \(P_3\) problem in cubic graphs
- Admission control with advance reservations in simple networks
- 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
- Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem
- Query-competitive sorting with uncertainty
- An approximation algorithm for \(P\)-prize-collecting set cover problem
- 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
- Hitting forbidden minors: approximation and kernelization
- A survey on combinatorial optimization in dynamic environments
- On Residual Approximation in Solution Extension Problems
- Design of dynamic algorithms via primal-dual method
- Primal-Dual Schema for Capacitated Covering Problems
- Combinatorial model and bounds for target set selection
- PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
- On the approximability and hardness of minimum topic connected overlay and its special instances
- Resource allocation problem under single resource assignment
- Improved algorithm for resource allocation problems
- Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
- A fixed-parameter algorithm for the vertex cover P₃ problem
- LP-based covering games with low price of anarchy
- Efficient online linear optimization with approximation algorithms
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- A water-filling primal-dual algorithm for approximating nonlinear covering problems
- Distributed set cover approximation: primal-dual with optimal locality
- Static routing in stochastic scheduling: performance guarantees and asymptotic optimality
- The multi‐integer set cover and the facility terminal cover problem
- 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
- Approximating the discrete time-cost tradeoff problem with bounded depth
- Approximating the discrete time-cost tradeoff problem with bounded depth
- On the primer selection problem in polymerase chain reaction experiments
- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
- Competitive vertex recoloring. (Online disengagement)
- Computing connected-k-subgraph cover with connectivity requirement
- Distributed half-integral matching and beyond
- Online and Approximate Network Construction from Bounded Connectivity Constraints
- Distributed half-integral matching and beyond
- A unified approach to approximating partial covering problems
- Approximability of sparse integer programs
- A primal-dual approximation algorithm for the vertex cover P^3 problem
- Hitting sets when the shallow cell complexity is small
- Online multiset submodular cover
- Distributed algorithms for covering, packing and maximum weighted matching
- Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
- Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
- A simple LP-free approximation algorithm for the minimum weight vertex cover problem
- Preserving approximation in the min-weighted set cover problem
- Primal-dual approximation algorithms for integral flow and multicut in trees
- A (2+)-factor approximation algorithm for split vertex deletion
- A water-filling primal-dual algorithm for approximating nonlinear covering problems
- Approximation algorithm for prize-collecting hypergraph vertex cover with fairness constraints
- Towards distributed two-stage stochastic optimization
- The complexity of Boolean failure identification
- Combination of parallel machine scheduling and vertex cover
- Approximate monotone local search for weighted problems
- Approximation algorithm for prize-collecting weighted set cover with fairness constraints
- An approximation algorithm for the k-prize-collecting hitting set problem
- Protecting the connectivity of a graph under non-uniform edge failures
- Colorful vertex recoloring of bipartite graphs
- Protecting the connectivity of a graph under nonuniform edge failures
- Approximation algorithms for the partition vertex cover problem
- A randomised approximation algorithm for the hitting set problem
- Primal-dual schema for capacitated covering problems
- On approximation problems related to the independent set and vertex cover problems
This page was built for publication: A linear-time approximation algorithm for the weighted vertex cover problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3910012)
