Question about Weighted Vertex Cover algorithm
Hi,
I need to generalize the algorithm given in CLRS book for vertex cover
problem and then show that for every C>0 exists a graph with weights
(each vertex has a weight) for which this expantion of the algorithm
gives a solution C times worst than the optimal one.
I think I found a way to generalize it but it's a 2 Approximation
algorithm, so it can't have a grapsh for which the solution is C times
worst since C might be bigger than 2.
Any ideas?
Thanks,
Eliko
.
Relevant Pages
 Re: Problem on an nxn grid
... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudocode ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ... (sci.math)  RE: [REPORT] cfsv4 vs sd0.44
... The definition for proportional fairness assumes that each thread has a ... threads have fixed weights throughout the interval. ... approximate this ideal scheduler (often referred to as Generalized ... The goal of a proportionalshare scheduling algorithm is to minimize the ... (LinuxKernel)  Re: Compressing your levels
... the algorithm (with a modified function ... One should probably count the weights ... you run seam removal to remove excess portions ... another portion of the dungeon is removed? ... (rec.games.roguelike.development)  finding shortest path...
... G = unoriented labeled connected graph G with n vertices and maximal ... Then the edges must be labeled by random weights from ... Output of the algorithm: ... The sequential algorithm is of type BBDFS with the search depth ... (comp.programming)  Re: Graph optimization
... represented in the form of a graph. ... I have to add up all the weights to form the ... algorithm is going to be the best for finding the shortest path ... (comp.programming) 
