Greedy algorithms and poset matroids

2013/06/17 by Luca Ferrari, Ferrari, Luca
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.DS #math.CO

paper · pdf · doi:10.48550/arxiv.1306.3797

arxiv created 2013/06/17 · arxiv updated 2013/06/18

Abstract

We generalize the matroid-theoretic approach to greedy algorithms to the setting of poset matroids, in the sense of Barnabei, Nicoletti and Pezzoli (1998) [BNP]. We illustrate our result by providing a generalization of Kruskal algorithm (which finds a minimum spanning subtree of a weighted graph) to abstract simplicial complexes.

Related

• A Formal Analysis of Algorithms for Matroids and Greedoids
• Coloring games and algebraic problems on matroids
• Extension of Simple Algorithms to the Matroid Secretary Problem
• Greedy weights for matroids
• Submodular Maximization Under A Matroid Constraint: Asking more from an old friend, the Greedy Algorithm