Title: Theory / Unimportant / CS / Algo / Approximation / Vazirani +18{ / 1 Combinatorial
Tags: récupéré algoToProblem computer_to_instruction hasNotNewEffectReturnsMeaning

Page: 1
Effect: find a minimum cost vertex cover
Variables: \(G=(V,E)\) an undirected graph
\(c:V\to\mathbb Q^+\) a cost function
Extra: Problem
Name: Vertex Cover

Name: A vertex cover of \(G\)
Definition: A subset \(V'\subseteq V\) such that each edge is incident to an element of \(V'\)
Page: 1
Variables: \(G=(V,E)\) an undirected graph
\(c:V\to\mathbb Q^+\) a cost function
Extra: dominating

Question: Cardinality vertex cover problem
Answer: vertex cover, with \(c(v)=1\)
Page: 1
Variables: \(G=(V,E)\) an undirected graph
\(c:V\to\mathbb Q^+\) a cost function
Intuition: Problem