scientific article; zbMATH DE number 3904328
[For the entire collection see Zbl 0533.00035.] The author shows that submodular set functions play a similar role in discrete optimization as convex functions in continuous optimization. In particular, a polynomial time algorithm to find the minimum of a submodular set function can be obtained. After giving some basic definitions and many examples from different fields the author turns to operations on submodular functions, which yield new submodular functions. In particular extensions of submodular functions are summarized. Then integrality properties of polyhedra related to submodular functions are derived and further results (for example the Matroid Intersection Theorem) are outlined. In the subsequent two sections the author shows the close relationship between submodular and convex functions on the one side and moreover that submodular functions resemble also features of concave functions. Finally optimization problems with submodular objective functions are discussed in short, in particular the submodular flow problem. Open problems and hints for further research conclude this survey paper.
- On the moments and distribution of discrete Choquet integrals from continuous distributions
- Maximization of submodular functions: theory and enumeration algorithms
- Scheduling multiprocessor UET tasks of two sizes
- A note on submodular set cover on matroids
- A Mazur-Orlicz type theorem for submodular set functions
- Greedy concepts for network flow problems
- An out-of-kilter method for submodular flows
- Submodular set functions and monotone systems in aggregation problems. I
- Submodular set functions and monotone systems in aggregation problems. II
- Sandwich theorems for set functions
- Generalized polymatroids and submodular flows
- Optimization over the polyhedron determined by a submodular function on a co-intersecting family
- Directed submodularity, ditroids and directed submodular flows
- Recognition problems for special classes of polynomials in 0-1 variables
- Applications of relaxed submodularity
- A submodular approach to discrete dynamic programming
- Context dependent probabilistic choice models based on measures of binary advantage
- Submodular functions and optimization
- Connectivity of submodular functions
- Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
- Discrete convex analysis
- The boundaries of submodular functions
- An ordered independence system and its applications to scheduling problems
- A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem
- Equilibrium in a market of intellectual goods
- Equilibrium analysis of an economy with innovations
- Submodular functions in problems of synthesis of networks
- An inequality for polymatroid functions and its applications.
- A greedy algorithm for convex geometries
- New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities.
- Application of M-convex submodular flow problem to mathematical economics
- K-submodular functions and convexity of their Lovász extension
- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Fast integer-valued algorithms for optimal allocations under constraints in stratified sampling
- Cores and Weber sets for fuzzy extensions of cooperative games
- \(k\)-additive aggregation functions and their characterization
- The intermediate set and limiting superdifferential for coalitional games: between the core and the Weber set
- A note on the Sobol' indices and interactive criteria
- The search value of a set
- A greedy algorithm for solving ordinary transportation problem with capacity constraints
- Phylogenetic flexibility via Hall-type inequalities and submodularity
- Polyhedral results for a class of cardinality constrained submodular minimization problems
- Aggregation-based extensions of fuzzy measures
- Maximization of the Choquet integral over a convex set and its application to resource allocation problems
- Discrete convexity and unimodularity. I.
- Bi-capacities. II: The Choquet integral
- A short convex-hull proof for the all-different system with the inclusion property
- Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2
- A combinatorial approach to level of repair analysis
- Extension of M-convexity and L-convexity to polyhedral convex functions
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A fully combinatorial algorithm for submodular function minimization.
- Separation of partition inequalities for the \((1,2)\)-survivable network design problem
- Quadratic M-convex and L-convex functions
- Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs
- A characterization of bisubmodular functions
- Lower probabilities and function representation
- Perspectives of Monge properties in optimization
- Explicit convex and concave envelopes through polyhedral subdivisions
- A laminarity property of the polyhedron described by a weakly posi-modular set function
- A discrete choice model when context matters
- Extremality of submodular functions
- Restricted strong convexity implies weak submodularity
- A strategic product for belief functions
- Integrals based on monotone set functions
- Strong formulations for conic quadratic optimization with indicator variables
- Approximation algorithms for the multiprocessor scheduling with submodular penalties
- Attribute based diversification of seeds for targeted influence maximization
- Sparse approximate solutions to max-plus equations
- An exact cutting plane method for k-submodular function maximization
- Solutions for non-negatively weighted TU games derived from extension operators
- Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens
- Discrete 2-convex functions
- Decreasing minimization on M-convex sets: background and structures
- Submodular functions and rooted trees
- Submodular function minimization and polarity
- Sequence independent lifting for a set of submodular maximization problems
- Asymptotic stability in replicator dynamics derived from TU games
- Multicriteria decision making based on bi-direction Choquet integrals
- Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
- Fractional 0-1 programming and submodularity
- Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
- Set-valued capacities: multi-agenda decision making
- Submodular optimization problems and greedy strategies: a survey
- Extension operators for TU games and the Lovász extension
- Extensions of fuzzy measures based on double generalization of the Lovász extension formula
- Buyer selection and service pricing in an electric fleet supply chain
- The median partition and submodularity
- Sparse optimization in feature selection: application in neuroimaging
- Polymatroid greedoids
- Fractional 0-1 programs: links between mixed-integer linear and conic quadratic formulations
- A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
- On the equality of integrals
- Asymptotic stability in the Lovász-Shapley replicator dynamic for cooperative games
- Game-theoretic derivation of upper hedging prices of multivariate contingent claims and submodularity
- A primal-dual algorithm for the minimum partial set multi-cover problem
- Properties of the \(d\)-dimensional Earth mover's problem
- A note on submodularity preserved involving the rank functions
- Approximation algorithms for vertex happiness
- On the probabilistic meaning of copula-based extensions of fuzzy measures. Applications to target-based utilities and multi-state reliability systems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3682236)