Covering Problems

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/3

encourage image

There's no tags or description

Looks like no tags are added yet.

Last updated 5:45 PM on 9/28/26
Name
Mastery
Learn
Test
Matching
Spaced
Call with Kai
Chat

No analytics yet

Send a link to your students to track their progress

4 Terms

1
New cards

Covering Prob

Given a combinatorial structure, how can it be covered with the lowest possible cost using a second structure?

2
New cards

Vertex Cover

  • In the Vertex Cover Problem, we want to cover all edges of a graph with as few nodes as possible.

  • FORMAL DEFINITION: Given a graph G(V,E), find a subset C ⊆ V of the nodes such that ∀e ∈ E : e ∩ C ̸= ∅.

  • VC is a hard optimization problem.

  • BRUTE FORCE Try all 2n subsets of nodes

  • The approximation algorithm provides a 2-approximation, i.e., a VC that is at most twice as large as OPT (optimal VC).


<ul><li><p>In the Vertex Cover Problem, we want to cover all edges of a graph with as few nodes as possible.</p></li><li><p>FORMAL DEFINITION: Given a graph G(V,E), find a subset C ⊆ V of the nodes such that ∀e ∈ E : e ∩ C ̸= ∅.</p></li><li><p>VC is a hard optimization problem.</p></li><li><p>BRUTE FORCE Try all 2n subsets of nodes</p></li><li><p>The approximation algorithm provides a 2-approximation, i.e., a VC that is at most twice as large as OPT (optimal VC).</p></li></ul><p></p>
3
New cards

Set Cover

  • FORMAL DEFINITION: Given a set U (the universe) and a collection S of subsets of U, find a subset S′ of S such that UnionS∈S′ S = U.

  • Find the smallest possible S′ that is a Set Cover for U.

  • Vertex Cover is a special case of Set Cover.

  • Covering points P with circular disks (or other geometric objects) is also a special case of Set Cover.

  • The greedy algorithm provides an O(log n) approximation.


<ul><li><p>FORMAL DEFINITION: Given a set U (the universe) and a collection S of subsets of U, find a subset S′ of S such that UnionS∈S′ S = U.</p></li><li><p>Find the smallest possible S′ that is a Set Cover for U.</p></li><li><p>Vertex Cover is a special case of Set Cover.</p></li><li><p>Covering points P with circular disks (or other geometric objects) is also a special case of Set Cover.</p></li><li><p>The greedy algorithm provides an O(log n) approximation.</p></li></ul><p></p>
4
New cards

Hitting Set

In a hitting set problem, we want to find representatives for a collection of subsets of a universe such that each set is represented.

FORMAL DEFINITION: Given a set U (the universe) and a collection S of subsets of U, find a subset U′ of U, such that ∀S ∈ S : S ∩ U′ ̸= ∅.

SC and HS are dual to each other.

Thus, any SC instance can be translated into an HS instance with the same solution and vice versa.