Submodular functions and optimization

Publication date: 17 September 1992

Published in: Annals of Discrete Mathematics (Search for Journal in Brave)

duality polymatroids separable convex optimization submodular functions submodular constraints submodular flows base polyhedra neoflows submodular systems supermodular systems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Nonlinear programming (90C30) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items

Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds, Polyhedra and optimization in connection with a weak majorization ordering, \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs, Unnamed Item, Discrete convexity and equilibria in economies with indivisible goods and money, A strongly polynomial time algorithm for a constrained submodular optimization problem, Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella., Greedy systems of linear inequalities and lexicographically optimal solutions, Applications of matroids in electric network theory, K-submodular functions and convexity of their Lovász extension, A network flow approach to cost allocation for rooted trees, Disjunctive analogues of submodular and supermodular pseudo-Boolean functions, Permutation polytopes corresponding to strongly supermodular functions, Core-based criterion for extreme supermodular functions, Convexity and Steinitz's exchange property, An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane, Quadratic M-convex and L-convex functions, A note on minimizing submodular functions, A fast cost scaling algorithm for submodular flow, Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form, A faster algorithm for computing the principal sequence of partitions of a graph, Even and odd marginal worth vectors, Owen's multilinear extension and convex games, A theorem on the principal structure for independent matchings, Dual greedy polyhedra, choice functions, and abstract convex geometries, Supermodular functions and the complexity of MAX CSP, A capacity scaling algorithm for convex cost submodular flows, Minimizing submodular functions over families of sets, Principal structure of submodular systems and Hitchcock-type independent flows, A characterization of bisubmodular functions, The membership problem in jump systems, A short proof of optimality of the bottom up algorithm for discrete resource allocation problems, How to compute least infeasible flows, Block triangularization of skew-symmetric matrices, Decomposition of a bidirected graph into strongly connected components and its signed poset structure, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Unnamed Item, Minimization of an M-convex function, Subcalculus for set functions and cores of TU games., Generalized roof duality and bisubmodular functions, Complexity of tropical Schur polynomials, A note on polylinking flow networks, A dichotomy for minimum cost graph homomorphisms, A strongly polynomial algorithm for line search in submodular polyhedra, Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems, Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability, A greedy algorithm for convex geometries, New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities., Improving graph partitions using submodular functions., Ideal multipartite secret sharing schemes, Graphic Submodular Function Minimization: A Graphic Approach and Applications, A greedy algorithm for some classes of integer programs., A laminarity property of the polyhedron described by a weakly posi-modular set function, Structural aspects of ordered polymatroids, A convex representation of totally balanced games, A unified approach to finding good stable matchings in the hospitals/residents setting, Application of M-convex submodular flow problem to mathematical economics, Adhesivity of polymatroids, An algorithm for the fair resource allocation problem with a submodular constraint, A polytope approach to the optimal assembly problem, Extremality of submodular functions, Ideal Secret Sharing Schemes for Useful Multipartite Access Structures, Equivalence of permutation polytopes corresponding to strictly supermodular functions, A submodular optimization problem with side constraints, A supermodular relaxation for scheduling with release dates, Note on pseudolattices, lattices and submodular linear programs, Sublattices of product spaces: Hulls, representations and counting, New algorithms for the intersection problem of submodular systems, \(M\)-convex functions and tree metrics, The Lovász extension of market games, Applications of discrete convex analysis to mathematical economics, On set functions that can be extended to convex functionals, Coordinatewise domain scaling algorithm for M-convex function minimization, Minimizing a sum of submodular functions, A capacity scaling algorithm for M-convex submodular flow, A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows, Log-supermodularity of weight functions, ordering weighted losses, and the loading monotonicity of weighted premiums, Combinatorial optimal control of semilinear elliptic PDEs, A Greedy Algorithm for Capacitated Lot-Sizing Problems, Canonical sequences of monotone measures, The core of games on convex geometries, On structures of bisubmodular polyhedra, Algorithmic aspects of a general modular decomposition theory, Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2, Traveling salesman games with the Monge property, Weak \(k\)-majorization and polyhedra, Fenchel-type duality for matroid valuations, Minimizing symmetric submodular functions, Base polytopes of series-parallel posets: Linear description and optimization, Discrete convex analysis, The English auction with differentiated commodities, Submodular containment is hard, even for networks, An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set, Extension of M-convexity and L-convexity to polyhedral convex functions, A necessary and sufficient condition for the convexity in oligopoly games, Polyhedral structure of submodular and posi-modular systems, Minimizing a submodular function arising from a concave function, A combinatorial algorithm minimizing submodular functions in strongly polynomial time., A fully combinatorial algorithm for submodular function minimization., A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources, A lexicographic algebraic theorem and its applications, Extreme points of the credal sets generated by comparative probabilities, Discrete polymatroids, A note on optimal covering augmentation for graphic polymatroids., Some recent results in the analysis of greedy algorithms for assignment problems, Decreasing minimization on base-polyhedra: relation between discrete and continuous cases, Separation of partition inequalities for the \((1,2)\)-survivable network design problem, Tight bounds for capacities, Parametric bisubmodular function minimization and its associated signed ring family, Bimonotone linear inequalities and sublattices of \(\mathbb R^n\)