A simple LP-free approximation algorithm for the minimum weight vertex cover problem

DOI10.1016/0020-0190(95)00022-5zbMath0875.68531OpenAlexW2057973628MaRDI QIDQ673599

Teofilo F. Gonzalez

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00022-5

zbMATH Keywords

Approximation algorithmsAnalysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

A computationally intractable problem on simplicial complexes

Cites Work

• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Efficient bounds for the stable set, vertex cover and set packing problems
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems

This page was built for publication: A simple LP-free approximation algorithm for the minimum weight vertex cover problem