Under Construction (PVC) MINIMUM PARTIAL VERTEX COVER Instance: Graph G=(V,E), for each vertex v in V a weight W(v)>=0; a number t>0; Solution: A t-vertex cover for G, i.e., a subset C of V such that, at lease t edges are covered by C ( |E(C)| >= t) Measure : W(C) (i.e. Sum {W(v): v in C}) +------------------------------------------------------------------+ | The "Local-Ratio Theorem" (oriented for PVC) | +------------------------------------------------------------------+ | If C is 2-approximation t-VC w.r.t the weight function W1 | | and C is 2-approximation t-VC w.r.t the weight function W2 | | then C is 2-approximation t-VC w.r.t the weight function W1+W2 | +------------------------------------------------------------------+ Our objective is to find a MINIMAL-t-VC C, i.e. C is an t-VC, but for each v in C: C-{v} is not t-VC. Define W1 to be epsilon HOMOGENEOUS, i.e. for all v in V: W1(v) = epsilon*Min(t,degree(v)) Q1: Every MINIMAL-FVS is 2-approximations w.r.t W1. Why? A1: See my paper from SODA99. +-------------------------------------------------------------------+ | Algorithm Partial_VC (G=(V,E),W,t) | +-------------------------------------------------------------------+ | If |E| 0 and C-{x} is t-VC for G | | then C=C-{x} | | Return C | +-------------------------------------------------------------------+ In the SODA99 paper, we generalize the problems so that the graph may be hypergraph (see PVC: Partial Set-Cover) and each edge have a "length" so we need length(E(C))>=t.