Title: Theory / Unimportant / CS / Algo / Approximation / Vazirani +18{
Tags: examplesSwitchExample1 fromAlgorithm hasNotNewEffectReturnsMeaning

Name: A matching
Definition: A subset \(M\subseteq F\) such that no two edges of \(M\) share an endpoint
Page: 3
Chapter: 1
Section: 1.1
Variables: \(H=(U,F)\) a graph

Name: A maximum matching
Definition: A matching of maximum cardinality
Page: 3
Chapter: 1
Section: 1.1
Variables: \(H=(U,F)\) a graph

Name: A maximal matching
Definition: maximal for inclusion
Page: 3
Chapter: 1
Section: 1.1
Variables: \(H=(U,F)\) a graph
Definition2: found by a greedy algorithm
Conjdef: A matching

Smaller0: [$]\abs{M}[/$]
Greater0: the cardinality of a maximum matching
Page: 3
Chapter: 1
Section: 1.1
Variables: \(H=(U,F)\) a graph
\(M\) a matching
Kind: Theo
Smaller to greater: \(2\le\)
Assuming: \(M\) is a maximal matching
Greater to smaller: \(\ge2\)

Name: A tight example
Definition: An infinite set of instances \(I\) for \(\Pi\) such that, for each such instance, [$]f_\Pi(I,s)=\delta(\abs{I})\cdot\mathrm{OPT}(I)[/$]
Page: 4
Chapter: 1
Section: 1.1
Variables: \(\Pi\) an optimisation problem
\(\mathrm{obj}_\Pi\) an objective function
\(\delta:\mathbb Z^+\to\mathbb Q^+\),
\(\mathcal A\) a factor \(\delta\) approximation algorithm for \(\Pi\)
Example: \(K_{n,n}\)
Applied to: cardinality vertex cover using maximal matching

Page: 4
Implementation: Find a maximal matching. Output the set of matched vertices
Section: 1.1
Chapter: 1
Effect: a \(\frac12\)-approximation for cardinality vertex cover
Variables: \(G\) a graph
Index: 2
Kind: Algo

Smaller0: \(G\) is bipartite
Greater0: the size of a maximal matching
Page: 4
Chapter: 1
Section: 1.1
Variables: \(G\) a graph
Index: 6
Kind: Theo
Greater1: the size of a minimal cover
Connect Greater0: =