Maximizing a class of submodular utility functions

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

Shabbir Ahmed, Atamtürk, Alper

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

polyhedracompetitive facility locationcombinatorial auctionsexpected utility maximizationsubmodular 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 (38)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Competitive facility location model with concave demand
• On a discrete nonlinear and nonseparable knapsack problem
• Submodularity and valid inequalities in capacitated fixed charge networks
• Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
• The 0-1 knapsack problem with a single continuous variable
• Sequence independent lifting in mixed integer programming
• Combinatorial auctions with decreasing marginal utilities
• On maximizing welfare when utility functions are subadditive
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Sequence Independent Lifting for Mixed-Integer Programming
• Resource Allocation to Interrelated Risky Projects Using a Multiattribute Utility Function
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Valid Inequalities and Superadditivity for 0–1 Integer Programs
• Characteristics of Decisions in Decision Analysis Practice

This page was built for publication: Maximizing a class of submodular utility functions