A greedy algorithm for convex geometries

DOI10.1016/S0166-218X(02)00467-5zbMath1030.90143MaRDI QIDQ1410695

Yoshio Okamoto, Kenji Kashiwabara

Publication date: 14 October 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Greedy algorithmSubmodularityAntimatroidConvex geometryExtreme set

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (2)

Dual greedy polyhedra, choice functions, and abstract convex geometries ⋮ The affine representation theorem for abstract convex geometries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Greedoids
• The theory of convex geometries
• Submodular functions and optimization
• Increasing the rooted connectivity of a digraph by one
• K-submodular functions and convexity of their Lovász extension
• Submodular linear programs on forests
• Structural aspects of ordered polymatroids
• An algorithmic characterization of antimatroids
• An order-theoretic framework for the greedy algorithm with applications to the core and Weber set of cooperative games

This page was built for publication: A greedy algorithm for convex geometries