Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints
From MaRDI portal
Publication:5245021
DOI10.1287/moor.2014.0668zbMath1308.90153OpenAlexW2057098288MaRDI QIDQ5245021
Publication date: 1 April 2015
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/55e96bb016bb0ede3aa5557196cde138e26b4b82
submodular functionpolynomial-time approximation schemebudget constraintsdiscrete concave functiongross substitutes utility
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Budgeted matching and budgeted matroid intersection via the gasoline puzzle
- Convexity and Steinitz's exchange property
- Generalized polymatroids and submodular flows
- Valuated matroids
- Discrete convex analysis
- Walrasian equilibrium with gross substitutes
- New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities.
- Application of M-convex submodular flow problem to mathematical economics
- A note on maximizing a submodular set function subject to a knapsack constraint
- Extension of M-convexity and L-convexity to polyhedral convex functions
- Combinatorial auctions with decreasing marginal utilities
- M-Convex Function on Generalized Polymatroid
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- A threshold of ln n for approximating set cover
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Approximation Schemes for Multi-Budgeted Independence Systems
- ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
- Combinatorial Optimization with Rational Objective Functions
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- Job Matching, Coalition Formation, and Gross Substitutes
- Valuated Matroid Intersection I: Optimality Criteria
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- On Maximizing Welfare When Utility Functions Are Subadditive
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- A Note on Kelso and Crawford's Gross Substitutes Condition
