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)  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)  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) 
