A better approximation ratio for the vertex cover problem
From MaRDI portal
Publication:2930267
DOI10.1145/1597036.1597045zbMath1298.68295OpenAlexW2030970869WikidataQ56338027 ScholiaQ56338027MaRDI QIDQ2930267
Publication date: 18 November 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1597036.1597045
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, Approximating Bounded Degree Deletion via Matroid Matching, Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation, On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs, Reinforcement learning for combinatorial optimization: a survey, Approximation for vertex cover in \(\beta\)-conflict graphs, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Approximating power node-deletion problems, Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry, Some Inverse Traveling Salesman Problems, Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs, Vertex cover in conflict graphs, A parameterized approximation scheme for generalized partial vertex cover, On the partial vertex cover problem in bipartite graphs -- a parameterized perspective, The power of amortized recourse for online graph problems, Timeline cover in temporal graphs: exact and approximation algorithms, Approximating vertex cover in dense hypergraphs, Undercover: a primal MINLP heuristic exploring a largest sub-MIP, Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, Refined notions of parameterized enumeration kernels with applications to matching cut enumeration, Vertex Cover in Graphs with Locally Few Colors, Improved approximation algorithms for path vertex covers in regular graphs, The ordered covering problem, Wireless capacity with arbitrary gain matrix, Strong and weak edges of a graph and linkages with the vertex cover problem, Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs, Approximating Partially Bounded Degree Deletion on Directed Graphs, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1, Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
