GreedyAlgorithm TransversalMatroids Edmonds’IntersectionAlgorithm References Greedy Algorithm And Edmonds Matroid Intersection Algorithm Paul Wilhelm [email protected] Institutfu¨rMathematik Humboldt-Universita¨t zuBerlin July 17, 2010 PaulWilhelm (Math–HUBerlin) GreedyAlgorithm July17,2010 1/32 GreedyAlgorithm TransversalMatroids Edmonds’IntersectionAlgorithm References Content I 1 Greedy Algorithm Prerequisites Algorithm Feasibility In Matroids Proof ’Greedy ⇒ Matroid’ Proof ’Matroid ⇒ Greedy’ 2 Transversal Matroids Job Scheduling Job SchedulingProblem MathematicalDescribtion Transversal Matroids Definition Transversal Matroids Proof Greedy Algorithm In Transversal Matroids 3 Edmonds’ Intersection Algorithm PaulWilhelm (Math–HUBerlin) GreedyAlgorithm July17,2010 2/32 GreedyAlgorithm TransversalMatroids Edmonds’IntersectionAlgorithm References Content II Prerequisites Example Intersection OfTwo Matriods Algorithm Counterexample Intersection Of Three Matriods Complexity OfEdmonds’ Algorithm Outlook Correctnes of the Algorithm PaulWilhelm (Math–HUBerlin) GreedyAlgorithm July17,2010 3/32 GreedyAlgorithm TransversalMatroids Edmonds’IntersectionAlgorithm References Prerequisites Remind Independence System / Matroid (E,I) ∅⊆ I (nonempty) Y ⊆ I, X ⊆ Y ⇒ X ⊆ I (hereditary) X,Y ∈ I, |X| < |Y| ⇒ ∃y ∈ Y \X : X ∪{y} ∈I (augmentation) PaulWilhelm (Math–HUBerlin) GreedyAlgorithm July17,2010 4/32 GreedyAlgorithm TransversalMatroids Edmonds’IntersectionAlgorithm References Prerequisites Remind Independence System / Matroid (E,I) ∅⊆ I (nonempty) Y ⊆ I, X ⊆ Y ⇒ X ⊆ I (hereditary) X,Y ∈ I, |X| < |Y| ⇒ ∃y ∈ Y \X : X ∪{y} ∈I (augmentation) PaulWilhelm (Math–HUBerlin) GreedyAlgorithm July17,2010 4/32 GreedyAlgorithm TransversalMatroids Edmonds’IntersectionAlgorithm References Prerequisites Remind Independence System / Matroid (E,I) ∅⊆ I (nonempty) Y ⊆ I, X ⊆ Y ⇒ X ⊆ I (hereditary) X,Y ∈ I, |X| < |Y| ⇒ ∃y ∈ Y \X : X ∪{y} ∈I (augmentation) PaulWilhelm (Math–HUBerlin) GreedyAlgorithm July17,2010 4/32 GreedyAlgorithm TransversalMatroids Edmonds’IntersectionAlgorithm References Prerequisites Min/Max - Problem (due to (Korte and Vygen, 2007, p. 306)) Maximization Problem Find X ∈ I s.t. the weight w(X) = w(e) is maximum eP∈X Minimization Problem Find a basis B s.t. the weight w(X) = w(e) is minimum eP∈X PaulWilhelm (Math–HUBerlin) GreedyAlgorithm July17,2010 5/32 GreedyAlgorithm TransversalMatroids Edmonds’IntersectionAlgorithm References Prerequisites Min/Max - Problem (due to (Korte and Vygen, 2007, p. 306)) Maximization Problem Find X ∈ I s.t. the weight w(X) = w(e) is maximum eP∈X Minimization Problem Find a basis B s.t. the weight w(X) = w(e) is minimum eP∈X PaulWilhelm (Math–HUBerlin) GreedyAlgorithm July17,2010 5/32 GreedyAlgorithm TransversalMatroids Edmonds’IntersectionAlgorithm References Prerequisites Min/Max - Problem (due to (Korte and Vygen, 2007, p. 306)) Maximization Problem Find X ∈ I s.t. the weight w(X) = w(e) is maximum eP∈X Minimization Problem Find a basis B s.t. the weight w(X) = w(e) is minimum eP∈X PaulWilhelm (Math–HUBerlin) GreedyAlgorithm July17,2010 5/32 GreedyAlgorithm TransversalMatroids Edmonds’IntersectionAlgorithm References Prerequisites Examples Many combinatorial optimization problems can be formulated as min/max-problem (more in (Korte and Vygen, 2007, p. 306)): maximum weight stable set travelling salesman shortest path knapsack minimum spanning tree maximum weight forest steiner tree maximum weight branching maximum weight matching job scheduling PaulWilhelm (Math–HUBerlin) GreedyAlgorithm July17,2010 6/32