Maximizing a class of submodular utility functions

DOI10.1007/s10107-009-0298-1zbMath1218.90221OpenAlexW2109974898MaRDI QIDQ543403

Publication date: 17 June 2011

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-009-0298-1

zbMATH Keywords

polyhedra competitive facility location combinatorial auctions expected utility maximization submodular function maximization

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Utility theory (91B16) Auctions, bargaining, bidding and selling, and other market models (91B26)

Related Items

Sequence Independent Lifting for the Set of Submodular Maximization Problem, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, A Branch-and-Cut Algorithm for Submodular Interdiction Games, Fractional 0-1 programming and submodularity, A polyhedral approach to bisubmodular function minimization, A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice, An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions, Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint, A survey on bilevel optimization under uncertainty, Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints, The stochastic pseudo-star degree centrality problem, Chance-constrained set covering with Wasserstein ambiguity, Submodular optimization problems and greedy strategies: a survey, Supermodularity and valid inequalities for quadratic optimization with indicators, Interactive optimization of submodular functions under matroid constraints, Submodularity in Conic Quadratic Mixed 0–1 Optimization, A scenario decomposition algorithm for 0-1 stochastic programs, A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions, A two-stage stochastic programming approach for influence maximization in social networks, New solution approaches for the maximum-reliability stochastic network interdiction problem, Maximizing a class of submodular utility functions with constraints, Supermodular covering knapsack polytope, Polyhedral results for a class of cardinality constrained submodular minimization problems, Outer approximation and submodular cuts for maximum capture facility location problems with random utilities, An approximation algorithm for a competitive facility location problem with network effects, Maximizing expected utility over a knapsack constraint, Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra, Route optimization for multiple searchers, Monotone submodular maximization over the bounded integer lattice with cardinality constraints, Successive Quadratic Upper-Bounding for Discrete Mean-Risk Minimization and Network Interdiction, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, An exact cutting plane method for \(k\)-submodular function maximization, Special issue: Global solution of integer, stochastic and nonconvex optimization problems, Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems, Submodular function minimization and polarity, Sequence independent lifting for a set of submodular maximization problems, Dynamic node packing, Two approximation algorithms for maximizing nonnegative weakly monotonic set functions

Cites Work