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