Abstract
A Simple LP-Free Approximation Algorithm for The Minimum WeightVertex Cover Problem
by: Teofilo F. Gonzalez
Abstract:
We present a simple LP-free (i.e., not requiring linear programming)approximation algorithm for the minimum weight vertex cover problem. Our newapproximation algorithm does not need to solve a linear programming problem,nor such a formulation is needed to establish its approximation bound. Thealgorithm takes linear time with respect to the number of nodes and edges inthe graph, and generates solutions that are within twice the weight of aminimum weight vertex cover. Both the algorithm and its proof of correctnessare elegant and simple.
Keywords:
LP-free, vertex cover, approximation algorithms, linear timealgorithms.
Date:
August 5, 1993
Document: 1993-18
