wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

set_cover_red_blue (391B)


      1 # Red-blue set cover problem
      2 
      3 cf [carr2000red]
      4 
      5 You have a universe where some elements are red and others are blue
      6 
      7 You have a collection of sets and want to find a subfamily that covers all blue elements but covers a least number of red elements
      8 
      9 The question is how well can it be [approximated], compared to [set_cover_approximation]
     10 
     11 Up: [set_cover_problem]
     12 
     13 See also: [exact_matching]