Combinatorics (Fall 2010)/Duality, Matroid

From TCS Wiki
Revision as of 07:48, 3 January 2011 by 172.21.9.33 (talk)
Jump to navigation Jump to search

Duality

Consider the following LP:

[math]\displaystyle{ \begin{align} \text{maximize} && 7x_1+x_2+5x_3\\ \text{subject to} && x_1-x_2+3x_3 &\ge 10\\ && 5x_1-2x_2-x_3 &\ge 6\\ && x_1,x_2,x_3 &\ge 0 \end{align} }[/math]

Let [math]\displaystyle{ OPT }[/math] be the value of the optimal solution.


LP duality

Duality theorems

Matroid

Kruskal's greedy algorithm for MST

Matroids

Let [math]\displaystyle{ X }[/math] be a finite set and [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] be a family of subsets of [math]\displaystyle{ X }[/math]. A member set [math]\displaystyle{ S\in\mathcal{F} }[/math] is called maximal if [math]\displaystyle{ S\cup\{x\}\not\in\mathcal{F} }[/math] for any [math]\displaystyle{ x\in X\setminus S }[/math].

For [math]\displaystyle{ Y\subseteq X }[/math], denote [math]\displaystyle{ \mathcal{F}_Y=\{S\in\mathcal{F}\mid S\subseteq Y\} }[/math]. Clearly [math]\displaystyle{ \mathcal{F}_Y }[/math] is the restriction of [math]\displaystyle{ \mathcal{F} }[/math] over [math]\displaystyle{ 2^Y\, }[/math].

Definition
A set system [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] is a matroid if it satisfies:
  • (hereditary) if [math]\displaystyle{ T\subseteq S\in\mathcal{F} }[/math] then [math]\displaystyle{ T\in\mathcal{F} }[/math];
  • (matroid property) for every [math]\displaystyle{ Y\subseteq X }[/math], all maximal [math]\displaystyle{ S\in\mathcal{F}_Y }[/math] have the same [math]\displaystyle{ |S| }[/math].

Suppose [math]\displaystyle{ \mathcal{F} }[/math] is a matroid. Some matroid terminologies:

  • Each member set [math]\displaystyle{ S\in\mathcal{F} }[/math] is called an independent set.
  • A maximal independent subset of a set [math]\displaystyle{ Y\subset X }[/math], i.e., a maximal [math]\displaystyle{ S\in\mathcal{F}_Y }[/math], is called a basis of [math]\displaystyle{ Y }[/math].
  • The size of the maximal [math]\displaystyle{ S\in\mathcal{F}_Y }[/math] is called the rank of [math]\displaystyle{ Y }[/math], denoted [math]\displaystyle{ r(Y) }[/math].

Graph matroids

Linear matroids

Greedy algorithms on weighted matroids

Matroid intersections