An improved approximation algorithm for combinatorial auctions with submodular bidders

DOI10.1145/1109557.1109675zbMath1192.91102OpenAlexW4245400518MaRDI QIDQ3581517

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109675

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)

Related Items (30)

Single-Parameter Combinatorial Auctions with Partially Public Valuations ⋮ The Limitations of Optimization from Samples ⋮ Tight Approximation Bounds for Maximum Multi-coverage ⋮ Policies for risk-aware sensor data collection by mobile agents ⋮ Learning in auctions: regret is hard, envy is easy ⋮ Best-response dynamics in combinatorial auctions with item bidding ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions ⋮ Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order ⋮ A mobile multi-agent sensing problem with submodular functions under a partition matroid ⋮ Minimizing the total weighted completion time of fully parallel jobs with integer parallel units ⋮ Two-stage submodular maximization under knapsack and matroid constraints ⋮ Approximation algorithms for the partial assignment problem ⋮ Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ Truthful randomized mechanisms for combinatorial auctions ⋮ Santa Claus Meets Hypergraph Matchings ⋮ Limitations of VCG-based mechanisms ⋮ Scheduling to maximize participation ⋮ Inapproximability results for combinatorial auctions with submodular utility functions ⋮ Economic efficiency requires interaction ⋮ Scheduling to Maximize Participation ⋮ Approximation for maximizing monotone non-decreasing set functions with a greedy method ⋮ Limitations of randomized mechanisms for combinatorial auctions ⋮ Unnamed Item ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas ⋮ Dynamics of Profit-Sharing Games ⋮ Approximation algorithms for vertex happiness ⋮ Fractionally subadditive maximization under an incremental knapsack constraint ⋮ k-Submodular maximization with two kinds of constraints ⋮ Tight approximation bounds for maximum multi-coverage

This page was built for publication: An improved approximation algorithm for combinatorial auctions with submodular bidders