Improved approximation of maximum vertex cover
From MaRDI portal
Publication:2583713
DOI10.1016/j.orl.2005.03.006zbMath1080.90065OpenAlexW2073925702MaRDI QIDQ2583713
Publication date: 18 January 2006
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2005.03.006
Related Items
Cites Work
- Unnamed Item
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- A probabilistic analysis of the maximal covering location problem
- On approximation of max-vertex-cover
- Cardinality constrained path covering problems in grid graphs
- A threshold of ln n for approximating set cover
- Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Maxima for Graphs and a New Proof of a Theorem of Turán