Submodular functions and optimization.

Publication date: 17 October 2005

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

Full work available at URL: http://www.sciencedirect.com/science/book/9780444520869

Mathematics Subject Classification ID

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

The bipermutahedron, Some Results about the Contractions and the Pendant Pairs of a Submodular System, Adaptive Test Allocation for Outbreak Detection and Tracking in Social Contact Networks, Polyhedral Clinching Auctions for Two-Sided Markets, Submodular Functions: Learnability, Structure, and Optimization, Unnamed Item, Unnamed Item, Network Inspection for Detecting Strategic Attacks, M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System, On a Reduction for a Class of Resource Allocation Problems, Finding a Stable Allocation in Polymatroid Intersection, Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids, Unnamed Item, Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity, Hopf Monoids and Generalized Permutahedra, Old and new challenges in Hadamard spaces, Ehrhart theory of paving and panhandle matroids, Unnamed Item, Monotone diameter of bisubmodular polyhedra, Lexicographically optimal earliest arrival flows, Recent progress on integrally convex functions, A Note on a Two-Sided Discrete-Concave Market with Possibly Bounded Salaries, Optimal general factor problem and jump system intersection, Choquet integral optimisation with constraints and the buoyancy property for fuzzy measures, Pricing decisions with reference price effect and risk preference customers, Tractability of explaining classifier decisions, Subdivisions of generalized permutahedra, A Fast and Scalable Computational Framework for Large-Scale High-Dimensional Bayesian Optimal Experimental Design, On Submodular Search and Machine Scheduling, Discrete Midpoint Convexity, Approximation algorithms for the fault-tolerant facility location problem with submodular penalties, Bipartite secret sharing and staircases, Volumes of subset Minkowski sums and the Lyusternik region, Invariant $\varphi$-Minimal Sets and Total Variation Denoising on Graphs, Continuous Relaxation for Discrete DC Programming, Incomplete cooperative games with player-centered information, Efficient processing of $k$-regret minimization queries with theoretical guarantees, A simple characterization of assignment mechanisms on set constraints, Deformation cones of hypergraphic polytopes, An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint, Supermodularity and valid inequalities for quadratic optimization with indicators, Simultaneous eating algorithm and greedy algorithm in assignment problems, A combinatorial approximation algorithm for $k$-level facility location problem with submodular penalties, Generalized Permutohedra from Probabilistic Graphical Models, Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids, Randomized strategies for robust combinatorial optimization with approximate separation, Results on the algebraic matroid of the determinantal variety, Characterizations of the set of integer points in an integral bisubmodular polyhedron, Making Bipartite Graphs DM-Irreducible, Submodularity in Conic Quadratic Mixed 0–1 Optimization, Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints, The Complexity of Valued CSPs, Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization, Unnamed Item, The core of games on ordered structures and graphs, Unnamed Item, Discrete Convex Functions on Graphs and Their Algorithmic Applications, Discrete convexity and polynomial solvability in minimum 0-extension problems, Geometric Rescaling Algorithms for Submodular Function Minimization, Monotone submodular maximization over the bounded integer lattice with cardinality constraints, Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces, The Finite Matroid-Based Valuation Conjecture is False, A Hierarchical Model for Cooperative Games, Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications, Bases and Transforms of Set Functions, The Hopf monoid of orbit polytopes, Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function, Finding Submodularity Hidden in Symmetric Difference, Multiple Exchange Property for M^♮-Concave Functions and Valuated Matroids, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Active-set Methods for Submodular Minimization Problems, Convexity of graph-restricted games induced by minimum partitions, Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem, Integral with Respect to a Non Additive Measure: An Overview, Signed ring families and signed posets, A survey of fundamental operations on discrete convex functions of various kinds, On basic operations related to network induction of discrete convex functions, Contribution of Frantisek Matus to the research on conditional independence, Characterizations of solutions for games with precedence constraints, Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, An approximation algorithm for submodular hitting set problem with linear penalties, Maximizing the smallest eigenvalue of a symmetric matrix: a submodular optimization approach, Zonotopes and the LP-Newton method, Base polyhedra and the linking property, On a general framework for network representability in discrete optimization, Uniqueness of equilibria in atomic splittable polymatroid congestion games, Optimization problems with color-induced budget constraints, Remarkable polyhedra related to set functions, games and capacities, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Structural identifiability in low-rank matrix factorization, Matroid optimisation problems with nested non-linear monomials in the objective function, A parametric propagator for pairs of \textsc{Sum} constraints with a discrete convexity property, Reverse search for enumeration, A constructive proof for the induction of M-convex functions through networks, Matroids on convex geometries (cg-matroids), Lifted generalized permutahedra and composition polynomials, A bilevel programming problem with maximization of a supermodular function in the lower level, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Simple push-relabel algorithms for matroids and submodular flows, Lattice polyhedra and submodular flows, Computational geometric approach to submodular function minimization for multiclass queueing systems, Equivalence of convex minimization problems over base polytopes, Matroid rank functions and discrete concavity, Shortest bibranchings and valuated matroid intersection, An approximation algorithm for the dynamic facility location problem with submodular penalties, Identifying combinatorial valuations from aggregate demand, Optimality conditions for a bilevel matroid problem, An algorithm for $(n-3)$-connectivity augmentation problem: jump system approach, Poly-symmetry in processor-sharing systems, The search value of a set, A simple algorithm for finding a maximum triangle-free $2$-matching in subcubic graphs, Optimal shill bidding in the VCG mechanism, Solving discrete systems of nonlinear equations, On the set of imputations induced by the $k$-additive core, Matroids on convex geometries: subclasses, operations, and optimization, Monotone optimal control for a class of Markov decision processes, A proof of Cunningham's conjecture on restricted subgraphs and jump systems, A logarithmic approximation for polymatroid congestion games, Finding the maximum cut by the greedy algorithm, Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem., Stochastic block-coordinate gradient projection algorithms for submodular maximization, Fast approximation of matroid packing and covering, Systems of equations with a single solution, Robust combinatorial optimization under budgeted-ellipsoidal uncertainty, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, On the complexity of submodular function minimisation on diamonds, Valuated matroid-based algorithm for submodular welfare problem, A framework of discrete DC programming by discrete convex analysis, Rank functions of strict cg-matroids, Preserving coalitional rationality for non-balanced games, Containment of rumor spread by selecting immune nodes in social networks, Minimizing a monotone concave function with laminar covering constraints, The cone of supermodular games on finite distributive lattices, Simpler exchange axioms for M-concave functions on generalized polymatroids, A stronger multiple exchange property for $\mathrm{M}^{\natural }$-concave functions, A cost-scaling algorithm for $0-1$ submodular flows, Restricted strong convexity implies weak submodularity, Continuous relaxation for discrete DC programming, Greedy oriented flows, L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Supermodular covering knapsack polytope, Time bounds for iterative auctions: a unified approach by discrete convex analysis, Inheritance of convexity for partition restricted games, Polymatroids and mean-risk minimization in discrete optimization, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches, The expressive power of valued constraints: Hierarchies and collapses, A simple projection algorithm for linear programming problems, A note on $M$-convexity in polyhedral split decomposition of distances, The restricted core of games on distributive lattices: how to share benefits in a hierarchy, Combinatorial integer labeling theorems on finite sets with applications, Algebraic and topological closure conditions for classes of pseudo-Boolean functions, Vertices of Schubitopes, The expressive power of binary submodular functions, A compact representation for modular semilattices and its applications, Parametric monotone function maximization with matroid constraints, A note on submodular function minimization by Chubanov's LP algorithm, A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions, A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties, A competitive partnership formation process, Cone superadditivity of discrete convex functions, Polynomial combinatorial algorithms for skew-bisubmodular function minimization, Congestion games viewed from M-convexity, The complexity of minimizing the difference of two $M^{\natural}$-convex set functions, Some specially structured assemble-to-order systems, Submodular function minimization, Induction of M-convex functions by linking systems, The densest subgraph problem with a convex/concave size function, A new algorithm for the intersection of a line with the independent set polytope of a matroid, $k$-trails: recognition, complexity, and approximations, Maximizing monotone submodular functions over the integer lattice, A general model for matroids and the greedy algorithm, Improved approximation algorithms for the facility location problems with linear/submodular penalties, Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times, A faster strongly polynomial time algorithm for submodular function minimization, Minimization of locally defined submodular functions by optimal soft arc consistency, Rooted $k$-connections in digraphs, Ensuring the boundedness of the core of games with restricted cooperation, Polyhedra with the integer Carathéodory property, The replacement principle in networked economies with single-peaked preferences, Efficient, fair, and strategy-proof (re)allocation under network constraints, Discrete Fenchel duality for a pair of integrally convex and separable convex functions, Streaming Algorithms for Submodular Function Maximization, Universal Tutte polynomial, Constrained flow control in storage networks: capacity maximization and balancing, Matroids of gain graphs in applied discrete geometry, Approximation Algorithms for the Multilevel Facility Location Problem with Linear/Submodular Penalties, Experimental Design for Nonparametric Correction of Misspecified Dynamical Models, The Expressive Power of Binary Submodular Functions, Matroid bases with cardinality constraints on the intersection, Choquet-based optimisation in multiobjective shortest path and spanning tree problems, Resolution of ideals associated to subspace arrangements, Fair integral submodular flows, Finding Cheeger cuts in hypergraphs via heat equation, An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties, Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties, Every finite distributive lattice is isomorphic to the minimizer set of an $M^\natural $-concave set function, Inheritance of convexity for the $\mathcal{P}_{\min}$-restricted game, Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost, Fair allocation of indivisible goods: beyond additive valuations, Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes, Submodular functions: from discrete to continuous domains, On additive approximate submodularity, Packing of arborescences with matroid constraints via matroid intersection, Online risk-averse submodular maximization, A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice, A generalized-polymatroid approach to disjoint common independent sets in two matroids, Strategyproof allocation mechanisms with endowments and M-convex distributional constraints, The holographic entropy cone from marginal independence, Streaming submodular maximization under $d$-knapsack constraints, The Mixed Evacuation Problem, Speech corpora subset selection based on time-continuous utterances features, On the foundations and extremal structure of the holographic entropy cone, A ranking model for the greedy algorithm and discrete convexity, Activity preserving graph simplification, A Survey on Covering Supermodular Functions, Theory of Principal Partitions Revisited, Recent Developments in Discrete Convex Analysis, The Expressive Power of Valued Constraints: Hierarchies and Collapses, Inequalities on submodular functions via term rewriting, Lorentzian polynomials, Cuts in undirected graphs. II, A note on M-convex functions on jump systems, Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach, A nonpositive curvature property of modular semilattices, The Hopf monoid and the basic invariant of directed graphs, Approximations of Lovász extensions and their induced interaction index, Polynomial-time algorithms for submodular Laplacian systems, Compression of $\mathrm{M}^\natural$-convex functions -- flag matroids and valuated permutohedra, A unifying look at sequence submodularity, A Primal-Dual Algorithm for Weighted Abstract Cut Packing, Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions, Extended random assignment mechanisms on a family of good sets, Minimum non-submodular cover problem with applications, The median partition and submodularity, Dijkstra's algorithm and L-concave function maximization, On the restricted cores and the bounded core of games on distributive lattices, A general two-sided matching market with discrete concave utility functions, Robust budget allocation via continuous submodular functions, Non-monotone submodular function maximization under $k$-system constraint, Approximation algorithms for the submodular edge cover problem with submodular penalties, A simple construction of complete single-peaked domains by recursive tiling, Degrees of freedom in submodular regularization: a computational perspective of Stein's unbiased risk estimate, Even factors, jump systems, and discrete convexity, On the vertices of the $k$-additive core, Approximation algorithms for the multiprocessor scheduling with submodular penalties, Integrality of subgradients and biconjugates of integrally convex functions, Game-theoretic derivation of upper hedging prices of multivariate contingent claims and submodularity, Symmetric submodular system: contractions and Gomory-Hu tree, SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION, On $k$-Submodular Relaxation, Efficient search for informational cores in complex systems: application to brain networks, Coxeter submodular functions and deformations of Coxeter permutahedra, Matroid optimization problems with monotone monomials in the objective, Diverse data selection via combinatorial quasi-concavity of distance covariance: a polynomial time global minimax algorithm, Set function optimization, Hardness results for multimarginal optimal transport problems, Exact and approximation algorithms for weighted matroid intersection, Online Linear Optimization for Job Scheduling Under Precedence Constraints, Optimization Problems with Color-Induced Budget Constraints, On a General Framework for Network Representability in Discrete Optimization, A new look at Popoviciu's concept of convexity for functions of two variables, Graft analogue of general Kotzig-Lovász decomposition, Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties, Submodular optimization views on the random assignment problem, Polymatroid-based capacitated packing of branchings, A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem, Discrete 2-convex functions, Decreasing minimization on M-convex sets: background and structures, Decreasing minimization on M-convex sets: algorithms and applications, Generalized skew bisubmodularity: a characterization and a min-max theorem, Bisubmodular polyhedra, simplicial divisions, and discrete convexity, Dual consistent systems of linear inequalities and cardinality constrained polytopes, Submodular function minimization and polarity, Sequence independent lifting for a set of submodular maximization problems, Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem, Attributes, Note on the polyhedral description of the Minkowski sum of two L-convex sets, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties