A General Class of Greedily Solvable Linear Programs

摘要: A greedy algorithm solves a dual pair of linear programs where the primal variables are associated to elements sublattice B finite product lattice, and cost coefficients define submodular function on B. This approach links generalizes two well-known classes greedily solvable programs. The problem ordinary multi-index transportation problems satisfying Monge condition Hoffman 1963; Bein et al. 1995 case forbidden cells nonforbidden form sublattice. an arbitrary lattice optimization over polyhedra Lovasz 1983; Fujishige Tomizawa 1983, which stemmed from work Edmonds 1970 polymatroids. Our model results also encompass pairs their solutions defined by 1983 for special Boolean algebra, Faigle Kern 1996 so-called "rooted forests." We discuss relationships between properties submodularity, present class with costs arising in production logistics.