Approximate composable truthful mechanism design

DOI10.1016/j.tcs.2016.02.025zbMath1353.91021OpenAlexW2283879421MaRDI QIDQ344791

Deshi Ye, Guo-Chuan Zhang

Publication date: 24 November 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.02.025

zbMATH Keywords

approximation algorithmsmechanism designknapsack auction

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online multiple-strip packing
• There is no EPTAS for two-dimensional knapsack
• Maximizing the total profit of rectangles packed into a rectangle
• Computationally-feasible truthful auctions for convex bundles
• Truthful approximation mechanisms for restricted combinatorial auctions
• The Multiple Subset Sum Problem
• Algorithmic mechanism design (extended abstract)
• An Online Mechanism for Resource Allocation and Pricing in Clouds
• Approximating the Non-contiguous Multiple Organization Packing Problem
• Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem
• Approximation Techniques for Utilitarian Mechanism Design
• Truth revelation in approximately efficient combinatorial auctions
• Approximation Algorithms for Multiple Strip Packing
• Parameterized Approximation Scheme for the Multiple Knapsack Problem
• Truthful Mechanisms via Greedy Iterative Packing
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• STACS 2004
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Approximate algorithms to pack rectangles into several strips
• STACS 2005