A linear-time approximation algorithm for the weighted vertex cover problem
From MaRDI portal
Cited in
(only showing first 100 items - show all)- On the multi-radius cover problem
- Online budgeted maximum coverage
- The set covering problem revisited: an empirical study of the value of dual information
- Improved algorithm for resource allocation problems
- A simple LP-free approximation algorithm for the minimum weight vertex cover problem
- Preserving approximation in the min-weighted set cover problem
- A graph approximation heuristic for the vertex cover problem on planar graphs
- Approximability of sparse integer programs
- New complexity results for the \(k\)-covers problem
- Capacitated domination problem
- A primal-dual approximation algorithm for \textsc{minsat}
- Minimum vertex cover in rectangle graphs
- Pareto optimality and a class of set covering heuristics
- Combinatorial model and bounds for target set selection
- A new fixed point approach for stable networks and stable marriages
- Approximation algorithm for prize-collecting weighted set cover with fairness constraints
- PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
- A fixed-parameter algorithm for the vertex cover P₃ problem
- An approximation algorithm for the k-prize-collecting hitting set problem
- An efficient fixed-parameter algorithm for 3-hitting set
- Iterative partial rounding for vertex cover with hard capacities
- Vertex cover meets scheduling
- A primal-dual approximation algorithm for the vertex cover P^3 problem
- Efficient algorithm for the vertex cover \(P_k\) problem on cacti
- O(f) bi-criteria approximation for capacitated covering with hard capacities
- On the approximability and hardness of minimum topic connected overlay and its special instances
- A survey on combinatorial optimization in dynamic environments
- Approximating the discrete time-cost tradeoff problem with bounded depth
- Approximating the discrete time-cost tradeoff problem with bounded depth
- A randomised approximation algorithm for the hitting set problem
- Hitting sets when the shallow cell complexity is small
- A bounded approximation for the minimum cost 2-sat problem
- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
- Distributed half-integral matching and beyond
- Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
- Efficient online linear optimization with approximation algorithms
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- Computing connected-\(k\)-subgraph cover with connectivity requirement
- A water-filling primal-dual algorithm for approximating nonlinear covering problems
- Static routing in stochastic scheduling: performance guarantees and asymptotic optimality
- Approximation algorithms for art gallery problems in polygons
- Combination of parallel machine scheduling and vertex cover
- Rounding to an integral program
- Resource allocation problem under single resource assignment
- Online multiset submodular cover
- A fast approximation algorithm for the multicovering problem
- The power of the weighted sum scalarization for approximating multiobjective optimization problems
- On residual approximation in solution extension problems
- Experimental analysis of approximation algorithms for the vertex cover and set covering problems
- Admission control with advance reservations in simple networks
- Primal-dual schema for capacitated covering problems
- Rounding algorithms for covering problems
- Dynamic algorithms via the primal-dual method
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- A factor 2 approximation algorithm for the vertex cover P₃ problem
- Network flow and 2-satisfiability
- A reduction tree approach for the discrete time/cost trade-off problem
- Online and Approximate Network Construction from Bounded Connectivity Constraints
- Approximation algorithms for the partition vertex cover problem
- Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
- Query-competitive sorting with uncertainty
- Heuristics for automated knowledge source integration and service composition
- Approximation algorithm for stochastic set cover problem
- A water-filling primal-dual algorithm for approximating nonlinear covering problems
- A (2+)-factor approximation algorithm for split vertex deletion
- The vertex cover \(P_3\) problem in cubic graphs
- Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
- A unified approach to approximating partial covering problems
- Distributed half-integral matching and beyond
- An experimental comparison of three heuristics for the WVCP
- The minimum substring cover problem
- On Residual Approximation in Solution Extension Problems
- Distributed set cover approximation: primal-dual with optimal locality
- Domination in Geometric Intersection Graphs
- Approximation algorithm for prize-collecting hypergraph vertex cover with fairness constraints
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Towards distributed two-stage stochastic optimization
- Complexity of the repeaters allocating problem
- Approximating the dense set-cover problem
- The Minimum Substring Cover Problem
- On approximation problems related to the independent set and vertex cover problems
- LP-based covering games with low price of anarchy
- Exploring further advantages in an alternative formulation for the set covering problem
- Approximation algorithms for hitting objects with straight lines
- Design of dynamic algorithms via primal-dual method
- Capacitated Domination Problem
- Primal-Dual Schema for Capacitated Covering Problems
- Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
- An approximation algorithm for \(P\)-prize-collecting set cover problem
- The multi‐integer set cover and the facility terminal cover problem
- The complexity of Boolean failure identification
- Approximation of the quadratic set covering problem
- Online and approximate network construction from bounded connectivity constraints
- New primal-dual algorithms for Steiner tree problems
- A general approximation method for bicriteria minimization problems
- Competitive vertex recoloring. (Online disengagement)
- Distributed algorithms for covering, packing and maximum weighted matching
- Efficient approximation algorithms for maximum coverage with group budget constraints
- On the primer selection problem in polymerase chain reaction experiments
- Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem
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)
