A Simple LP-Free Approximation Algorithm for The Minimum WeightVertex Cover Problem

Report ID: 
1993-18
Authors: 
Teofilo F. Gonzalez
Date: 
1993-08-01 05:00:00

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.

Document

File 1993-18.ps