A General Class of Greedily Solvable Linear Programs
研究了一类可被贪婪算法求解的线性规划对偶问题，其中原始变量与有限乘积格中的子格元素关联，成本系数定义次模函数，统一并推广了满足Monge条件的运输问题和次模多面体上的线性优化。
A greedy algorithm solves a dual pair of linear programs where the primal variables are associated to the elements of a sublattice B of a finite product lattice, and the cost coefficients define a submodular function on B. This approach links and generalizes two well-known classes of greedily solvable linear programs. The primal problem generalizes the (ordinary and multi-index) transportation problems satisfying a Monge condition (Hoffman 1963; Bein et al. 1995) to the case of forbidden cells where the nonforbidden cells form a sublattice. The dual problem generalizes to an arbitrary finite product lattice the linear optimization problem over submodular polyhedra (Lovász 1983; Fujishige and Tomizawa 1983), which stemmed from the work of Edmonds (1970) on polymatroids. Our model and results also encompass the dual pairs of linear programs and their greedy solutions defined by Lovász (1983) for the special case of the Boolean algebra, and by Faigle and Kern (1996) for the case of so-called “rooted forests.” We also discuss relationships between Monge properties and submodularity, and present a class of problems with submodular costs arising in production and logistics.