Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
From MaRDI portal
Publication:3149886
DOI10.1137/S0097539700381097zbMath1041.68130OpenAlexW1971749164MaRDI QIDQ3149886
Publication date: 29 September 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539700381097
Related Items
Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, An approximation algorithm for submodular hitting set problem with linear penalties, An edge-reduction algorithm for the vertex cover problem, Models of greedy algorithms for graph problems, Combinatorial Auctions with Conflict-Based Externalities, A primal-dual approximation algorithm for partial vertex cover: Making educated guesses, Combinatorial optimization. Abstracts from the workshop held November 9--15, 2014., A primal-dual approximation algorithm for \textsc{minsat}, On the Lovász Theta Function for Independent Sets in Sparse Graphs, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, On the weighted \(k\)-path vertex cover problem, Graph covering using bounded size subgraphs, On the approximability and hardness of minimum topic connected overlay and its special instances, On the Minimum Hitting Set of Bundles Problem, The power of amortized recourse for online graph problems, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost, Approximation of set multi-cover via hypergraph matching, Approximating vertex cover in dense hypergraphs, Local search with edge weighting and configuration checking heuristics for minimum vertex cover, The Approximability of Assortment Optimization Under Ranking Preferences, Undercover: a primal MINLP heuristic exploring a largest sub-MIP, Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, A primal-dual method for approximating tree cover with two weights, Vertex Cover in Graphs with Locally Few Colors, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), New complexity results for the \(k\)-covers problem, Unnamed Item, Minimum vertex cover in rectangle graphs, New tools and connections for exponential-time approximation, Reconstruction of Kauffman networks applying trees, On approximation of the vertex cover problem in hypergraphs, A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem, The ordered covering problem, Approximation algorithm for stochastic set cover problem, Improved approximation bounds for edge dominating set in dense graphs, Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs, Independent sets in bounded-degree hypergraphs, Strong and weak edges of a graph and linkages with the vertex cover problem, On the minimum hitting set of bundles problem, Randomized approximation for the set multicover problem in hypergraphs
