Greedy algorithms and poset matroids

DOI10.1016/J.JDA.2014.07.005zbMATH Open1308.68146arXiv1306.3797OpenAlexW2153770200MaRDI QIDQ473210FDOQ473210

Authors: L. Ferrari 

Publication date: 24 November 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1306.3797

Recommendations

• A framework for the greedy algorithm
• scientific article; zbMATH DE number 3871387
• Greedy Families for Linear Objective Functions
• Introduction to Greedoids
• Valuated matroids -- a new look at the greedy algorithm

zbMATH Keywords

greedy algorithmmatroidposetabstract simplicial complex

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Nonnumerical algorithms (68W05) Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• Introduction to algorithms.
• Title not available (Why is that?)
• A THEOREM ON INDEPENDENCE RELATIONS
• Matroids and the greedy algorithm
• Matroids on partially ordered sets
• A general model for matroids and the greedy algorithm
• The greedy algorithm for partially ordered sets
• Geometries on partially ordered sets
• On ordered languages and the optimization of linear functions by greedy algorithms

Cited In (3)

• Greedy-type resistance of combinatorial problems
• Generalized matroids based on three-way decision models
• Title not available (Why is that?)

This page was built for publication: Greedy algorithms and poset matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q473210)