A general model for matroids and the greedy algorithm

• 成果类型: Article
• 署名作者: Faigle, Ulrich; Fujishige, Satoru
• 署名单位: University of Cologne; Kyoto University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-008-0213-1
• 发表日期: 2009
• 页码: 353-369
• 关键词: geometries; core

摘要

We present a general model for set systems to be independence families with respect to set families which determine classes of proper weight functions on a ground set. Within this model, matroids arise from a natural subclass and can be characterized by the optimality of the greedy algorithm. This model includes and extends many of the models for generalized matroid-type greedy algorithms proposed in the literature and, in particular, integral polymatroids. We discuss the relationship between these general matroids and classical matroids and provide a Dilworth embedding that allows us to represent matroids with underlying partial order structures within classical matroids. Whether a similar representation is possible for matroids on convex geometries is an open question.