Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online

DOI10.1287/moor.2021.1208zbMath1498.91101arXiv1905.00848OpenAlexW2949691923MaRDI QIDQ5868957

Pieter Kleer, Georgios Amanatidis, Guido Schäfer

Publication date: 26 September 2022

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1905.00848

zbMATH Keywords

procurement auctionsnon-monotone submodular maximizationbudget-feasible mechanism designsubmodular knapsack secretary

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Mechanism design theory (91B03)

Cites Work

• Unnamed Item
• A note on maximizing a submodular set function subject to a knapsack constraint
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Simple and efficient budget feasible mechanisms for monotone submodular valuations
• Combinatorial auctions with decreasing marginal utilities
• Submodular secretary problem and extensions
• Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design
• Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
• Maximizing Non-monotone Submodular Functions
• Streaming Algorithms for Submodular Function Maximization
• On the Computational Power of Demand Queries
• A Knapsack Secretary Problem with Applications
• Optimal Auction Design
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• An analysis of approximations for maximizing submodular set functions—I
• Deterministic Algorithms for Submodular Maximization Problems
• Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
• On Budget-Feasible Mechanism Design for Symmetric Submodular Objectives
• The Submodular Secretary Problem Goes Linear
• Worst-Case Mechanism Design via Bayesian Analysis
• Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Prophet Inequalities with Limited Information
• Submodular Maximization with Cardinality Constraints
• Fast algorithms for maximizing submodular functions
• Budget Feasible Mechanisms for Experimental Design
• Budget feasible mechanism design
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Budget feasible mechanisms on matroids

This page was built for publication: Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online