Dual greedy polyhedra, choice functions, and abstract convex geometries

DOI10.1016/j.disopt.2004.03.004zbMath1087.90087MaRDI QIDQ2386212

Satoru Fujishige

Publication date: 22 August 2005

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2004.03.004

zbMATH Keywords

Submodularity; Convex geometry; Choice function; Dual greedy algorithm

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

Related Items

A Hierarchical Model for Cooperative Games, The affine representation theorem for abstract convex geometries, Note on pseudolattices, lattices and submodular linear programs, A general model for matroids and the greedy algorithm, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Dual consistent systems of linear inequalities and cardinality constrained polytopes, A ranking model for the greedy algorithm and discrete convexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Greedoids
• Choice functions over a finite set: A summary
• The theory of convex geometries
• Submodular functions and optimization
• Increasing the rooted connectivity of a digraph by one
• Choice functions and abstract convex geometries
• A greedy algorithm for convex geometries
• On the core of ordered submodular cost games
• K-submodular functions and convexity of their Lovász extension
• Submodular linear programs on forests
• Structural aspects of ordered polymatroids
• A General Class of Greedily Solvable Linear Programs
• A Note on Kelso and Crawford's Gross Substitutes Condition
• An order-theoretic framework for the greedy algorithm with applications to the core and Weber set of cooperative games