Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints (Q5245021): Difference between revisions

Latest revision as of 21:59, 9 July 2024

scientific article; zbMATH DE number 6422226

Language	Label	Description	Also known as
English	Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints	scientific article; zbMATH DE number 6422226

Statements

instance of

scholarly article

0 references

title

Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints (English)

0 references

author

Akiyoshi Shioura

0 references

published in

Mathematics of Operations Research

0 references

publication date

1 April 2015

0 references

full work available at URL

https://semanticscholar.org/paper/55e96bb016bb0ede3aa5557196cde138e26b4b82

0 references

zbMATH Keywords

discrete concave function

0 references

submodular function

0 references

budget constraints

0 references

gross substitutes utility

0 references

polynomial-time approximation scheme

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Budgeted matching and budgeted matroid intersection via the gasoline puzzle

0 references

Q3524720

0 references

Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)

0 references

Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

0 references

Q5365101

0 references

Submodular function maximization via the multilinear relaxation and contention resolution schemes

0 references

Valuated matroids

0 references

A threshold of ln <i>n</i> for approximating set cover

0 references

On Maximizing Welfare When Utility Functions Are Subadditive

0 references

A Unified Continuous Greedy Algorithm for Submodular Maximization

0 references

Generalized polymatroids and submodular flows

0 references

A Note on Kelso and Crawford's Gross Substitutes Condition

0 references

Approximation Schemes for Multi-Budgeted Independence Systems

0 references

Walrasian equilibrium with gross substitutes

0 references

Job Matching, Coalition Formation, and Gross Substitutes

0 references

Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints

0 references

Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints

0 references

Combinatorial auctions with decreasing marginal utilities

0 references

An Effective Heuristic Algorithm for the Traveling-Salesman Problem

0 references

Combinatorial Optimization with Rational Objective Functions

0 references

Q3632447

0 references

Convexity and Steinitz's exchange property

0 references

Valuated Matroid Intersection I: Optimality Criteria

0 references

Discrete convex analysis

0 references

M-Convex Function on Generalized Polymatroid

0 references

Extension of M-convexity and L-convexity to polyhedral convex functions

0 references

Application of M-convex submodular flow problem to mathematical economics

0 references

New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities.

0 references

ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS

0 references

A note on maximizing a submodular set function subject to a knapsack constraint

0 references

Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems

0 references

Identifiers

zbMATH Open document ID

1308.90153

0 references

DOI

10.1287/moor.2014.0668

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5245021

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2057098288
@@ Property / OpenAlex ID: W2057098288 / rank @@
+Normal rank
@@ Property / cites work @@
+Budgeted matching and budgeted matroid intersection via the gasoline puzzle
+Normal rank
@@ Property / cites work @@
+Q3524720
@@ Property / cites work: Q3524720 / rank @@
+Normal rank
@@ Property / cites work @@
+Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
+Normal rank
@@ Property / cites work @@
+Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
+Normal rank
@@ Property / cites work @@
+Q5365101
@@ Property / cites work: Q5365101 / rank @@
+Normal rank
@@ Property / cites work @@
+Submodular function maximization via the multilinear relaxation and contention resolution schemes
+Normal rank
@@ Property / cites work @@
+Valuated matroids
@@ Property / cites work: Valuated matroids / rank @@
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+On Maximizing Welfare When Utility Functions Are Subadditive
+Normal rank
@@ Property / cites work @@
+A Unified Continuous Greedy Algorithm for Submodular Maximization
+Normal rank
@@ Property / cites work @@
+Generalized polymatroids and submodular flows
@@ Property / cites work: Generalized polymatroids and submodular flows / rank @@
+Normal rank
@@ Property / cites work @@
+A Note on Kelso and Crawford's Gross Substitutes Condition
+Normal rank
@@ Property / cites work @@
+Approximation Schemes for Multi-Budgeted Independence Systems
+Normal rank
@@ Property / cites work @@
+Walrasian equilibrium with gross substitutes
@@ Property / cites work: Walrasian equilibrium with gross substitutes / rank @@
+Normal rank
@@ Property / cites work @@
+Job Matching, Coalition Formation, and Gross Substitutes
+Normal rank
@@ Property / cites work @@
+Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
+Normal rank
@@ Property / cites work @@
+Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
+Normal rank
@@ Property / cites work @@
+Combinatorial auctions with decreasing marginal utilities
+Normal rank
@@ Property / cites work @@
+An Effective Heuristic Algorithm for the Traveling-Salesman Problem
+Normal rank
@@ Property / cites work @@
+Combinatorial Optimization with Rational Objective Functions
+Normal rank
@@ Property / cites work @@
+Q3632447
@@ Property / cites work: Q3632447 / rank @@
+Normal rank
@@ Property / cites work @@
+Convexity and Steinitz's exchange property
@@ Property / cites work: Convexity and Steinitz's exchange property / rank @@
+Normal rank
@@ Property / cites work @@
+Valuated Matroid Intersection I: Optimality Criteria
+Normal rank
@@ Property / cites work @@
+Discrete convex analysis
@@ Property / cites work: Discrete convex analysis / rank @@
+Normal rank
@@ Property / cites work @@
+M-Convex Function on Generalized Polymatroid
@@ Property / cites work: M-Convex Function on Generalized Polymatroid / rank @@
+Normal rank
@@ Property / cites work @@
+Extension of M-convexity and L-convexity to polyhedral convex functions
+Normal rank
@@ Property / cites work @@
+Application of M-convex submodular flow problem to mathematical economics
+Normal rank
@@ Property / cites work @@
+New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities.
+Normal rank
@@ Property / cites work @@
+ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
+Normal rank
@@ Property / cites work @@
+A note on maximizing a submodular set function subject to a knapsack constraint
+Normal rank
@@ Property / cites work @@
+Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:5245021