scientific article
From MaRDI portal
Publication:3682236
zbMath0566.90060MaRDI QIDQ3682236
Publication date: 1983
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
surveypolynomial time algorithmdiscrete optimizationsubmodular set functionssubmodular flow problemintegrality properties of polyhedraMatroid Intersection Theorem
Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Polytopes and polyhedra (52Bxx)
Related Items
On \(b\)-bistochastic quadratic stochastic operators, K-submodular functions and convexity of their Lovász extension, An ordered independence system and its applications to scheduling problems, Core-based criterion for extreme supermodular functions, Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, A Mazur-Orlicz type theorem for submodular set functions, Quadratic M-convex and L-convex functions, The concave integral over large spaces, Greedy concepts for network flow problems, Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs, An out-of-kilter method for submodular flows, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem, Strong formulations for quadratic optimization with M-matrices and indicator variables, Equilibrium in a market of intellectual goods, Equilibrium analysis of an economy with innovations, A characterization of bisubmodular functions, Sandwich theorems for set functions, Enumerating disjunctions and conjunctions of paths and cuts in reliability theory, Fast integer-valued algorithms for optimal allocations under constraints in stratified sampling, 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, Lower probabilities and function representation, Recognition problems for special classes of polynomials in 0-1 variables, An FPTAS for optimizing a class of low-rank functions over a polytope, Perspectives of Monge properties in optimization, Matroids on convex geometries (cg-matroids), Cores and Weber sets for fuzzy extensions of cooperative games, A submodular approach to discrete dynamic programming, \(k\)-additive aggregation functions and their characterization, The intermediate set and limiting superdifferential for coalitional games: between the core and the Weber set, Axiomatizations of Lovász extensions of pseudo-Boolean functions, Subjective independence and concave expected utility, The arity gap of order-preserving functions and extensions of pseudo-Boolean functions, A note on the Sobol' indices and interactive criteria, The search value of a set, Approximability of sparse integer programs, 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., Explicit convex and concave envelopes through polyhedral subdivisions, Absolutely determined matrices, Bipolarization of posets and natural interpolation, Distribution functions of linear combinations of lattice polynomials from the uniform distribu\-tion, Is submodularity testable?, A discrete choice model when context matters, A greedy algorithm for solving ordinary transportation problem with capacity constraints, Context dependent probabilistic choice models based on measures of binary advantage, On the complexity of submodular function minimisation on diamonds, Phylogenetic flexibility via Hall-type inequalities and submodularity, A simple proof for the convexity of the Choquet integral, Valuated matroid-based algorithm for submodular welfare problem, Extremality of submodular functions, Sandwich games, Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions, Lifting cover inequalities for the precedence-constrained knapsack problem, Equivalence of permutation polytopes corresponding to strictly supermodular functions, Efficient minimization of higher order submodular functions using monotonic Boolean functions, Restricted strong convexity implies weak submodularity, Graph cuts with interacting edge weights: examples, approximations, and algorithms, Polyhedral results for a class of cardinality constrained submodular minimization problems, Sensor selection for Kalman filtering of linear dynamical systems: complexity, limitations and greedy algorithms, Submodular functions in graph theory, Connectivity of submodular functions, Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs, A discrete Choquet integral for ordered systems, Aggregation-based extensions of fuzzy measures, A strategic product for belief functions, Maximization of the Choquet integral over a convex set and its application to resource allocation problems, Algebraic and topological closure conditions for classes of pseudo-Boolean functions, The expressive power of binary submodular functions, Global optimization for first order Markov random fields with submodular priors, Pseudo-Boolean optimization, Discrete convexity and unimodularity. I., Bi-capacities. II: The Choquet integral, Monge extensions of cooperation and communication structures, Integrals based on monotone set functions, On set functions that can be extended to convex functionals, Generalized roof duality, Combinatorial optimal control of semilinear elliptic PDEs, A short convex-hull proof for the all-different system with the inclusion property, Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs, 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, On the moments and distribution of discrete Choquet integrals from continuous distributions, Maximization of submodular functions: theory and enumeration algorithms, Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case, Scheduling multiprocessor UET tasks of two sizes, Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2, Discrete convex analysis, A note on submodular set cover on matroids, A combinatorial approach to level of repair analysis, Extension of M-convexity and L-convexity to polyhedral convex functions, A note on Frank's generalized polymatroids, A combinatorial algorithm minimizing submodular functions in strongly polynomial time., A fully combinatorial algorithm for submodular function minimization., Fuzzy shortest paths, Separation of partition inequalities for the \((1,2)\)-survivable network design problem, Multicriteria decision making based on bi-direction Choquet integrals, Principal points analysis via p-median problem for binary data, Convexity and Steinitz's exchange property, The unwalked path between quasi-copulas and copulas: stepping stones in higher dimensions, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, Joint games and compatibility, The Expressive Power of Binary Submodular Functions, Structured Sparsity: Discrete and Convex Approaches, Separation of partition inequalities with terminals, Quantum machine learning: a classical perspective, Fractional 0-1 programming and submodularity, Submodular Functions: Learnability, Structure, and Optimization, Scarcity, competition, and value, Unnamed Item, Unnamed Item, The dual Lovász extension operator and the Shapley extension operator for TU games, Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties, Hub Location as the Minimization of a Supermodular Set Function, Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function, A short proof of convexity of step-out-step-in sequencing games, Multiproduct Newsvendor Problem with Customer-Driven Demand Substitution: A Stochastic Integer Program Perspective, A sub-modular receding horizon solution for mobile multi-agent persistent monitoring, Set-valued capacities: multi-agenda decision making, A mobile multi-agent sensing problem with submodular functions under a partition matroid, Submodular functions: from discrete to continuous domains, On additive approximate submodularity, Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds, Private Bayesian persuasion, Codes, lower bounds, and phase transitions in the symmetric rendezvous problem, A note on the implications of approximate submodularity in discrete optimization, A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice, Analyzing Residual Random Greedy for monotone submodular maximization, Lifted polymatroid inequalities for mean-risk optimization with indicator variables, Constrained Submodular Maximization via a Nonsymmetric Technique, Submodular optimization problems and greedy strategies: a survey, Computing Superdifferentials of Lovász Extension with Application to Coalitional Games, Monge properties, discrete convexity and applications, Unnamed Item, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Extension operators for TU games and the Lovász extension, A simple optimal contention resolution scheme for uniform matroids, Inequalities on submodular functions via term rewriting, Submodularity in Conic Quadratic Mixed 0–1 Optimization, Adhesivity of polymatroids, Continuous limits of discrete perimeters, Extensions of fuzzy measures based on double generalization of the Lovász extension formula, The Submodular Secretary Problem Goes Linear, Approximations of Lovász extensions and their induced interaction index, Buyer selection and service pricing in an electric fleet supply chain, Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm, A submodular optimization problem with side constraints, A supermodular relaxation for scheduling with release dates, The median partition and submodularity, Local minima, marginal functions, and separating hyperplanes in discrete optimization, A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid, Sparse optimization in feature selection: application in neuroimaging, The core of games on ordered structures and graphs, Polymatroid greedoids, Fractional 0-1 programs: links between mixed-integer linear and conic quadratic formulations, Characterizations ofk-Convex Games, Combinatorial auctions with decreasing marginal utilities, A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem, When are multidegrees positive?, Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces, On the equality of integrals, On the vertices of the \(k\)-additive core, Asymptotic stability in the Lovász-Shapley replicator dynamic for cooperative games, When are multidegrees positive?, Extensions of Capacities, Game-theoretic derivation of upper hedging prices of multivariate contingent claims and submodularity, Finding Submodularity Hidden in Symmetric Difference, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, A primal-dual algorithm for the minimum partial set multi-cover problem, Sparse approximate solutions to max-plus equations, Multicommodity flows and cuts in polymatroidal networks, Properties of the \(d\)-dimensional Earth mover's problem, An exact cutting plane method for \(k\)-submodular function maximization, Unnamed Item, Active-set Methods for Submodular Minimization Problems, A Mixed-Integer Fractional Optimization Approach to Best Subset Selection, Approximation algorithms for vertex happiness, Integral with Respect to a Non Additive Measure: An Overview, On the probabilistic meaning of copula-based extensions of fuzzy measures. Applications to target-based utilities and multi-state reliability systems, Stability and Recovery for Independence Systems, A survey of fundamental operations on discrete convex functions of various kinds, Solutions for non-negatively weighted TU games derived from extension operators, Coincidences of the concave integral and the pan-integral, 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, Choice functions in the intersection of matroids, Submodular functions and rooted trees, Generalized skew bisubmodularity: a characterization and a min-max theorem, One-adhesive polymatroids, Submodular function minimization and polarity, Sequence independent lifting for a set of submodular maximization problems, Unnamed Item, Asymptotic stability in replicator dynamics derived from TU games, An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties, Approximating power node-deletion problems, Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint, Möbius product-based constructions of aggregation functions, Inventory allocation with full downward substitution and monotone cost differences, Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints, Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness, THE ACTUATION SPECTRUM OF SPATIOTEMPORAL NETWORKS WITH POWER-LAW TIME DEPENDENCIES, Volumes of subset Minkowski sums and the Lyusternik region, Efficient processing of \(k\)-regret minimization queries with theoretical guarantees, A strongly polynomial time algorithm for a constrained submodular optimization problem, Discrete convexity and polynomial solvability in minimum 0-extension problems