Maximizing a class of submodular utility functions
From MaRDI portal
Publication:543403
DOI10.1007/s10107-009-0298-1zbMath1218.90221MaRDI 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
polyhedra; competitive facility location; combinatorial auctions; expected utility maximization; submodular function maximization
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
91B16: Utility theory
91B26: Auctions, bargaining, bidding and selling, and other market models
Related Items
Monotone submodular maximization over the bounded integer lattice with cardinality constraints, Maximizing a class of submodular utility functions with constraints, A two-stage stochastic programming approach for influence maximization in social networks, 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, New solution approaches for the maximum-reliability stochastic network interdiction problem, Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra, A scenario decomposition algorithm for 0-1 stochastic programs, Route optimization for multiple searchers, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
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