question about weighted vertex cover algorithm

Hi,

Hey people,


I need to generalize the algorithm given in CLRS book for vertex cover
problem to the weighted 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 for the right graph or a different algorithm?


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 pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • RE: [REPORT] cfs-v4 vs sd-0.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 proportional-share scheduling algorithm is to minimize the ...
    (Linux-Kernel)
  • 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 BB-DFS with the search depth ...
    (comp.programming)