Approximate composable truthful mechanism design

DOI10.1016/j.tcs.2016.02.025zbMath1353.91021MaRDI 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 algorithms; mechanism design; knapsack auction

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90C27: Combinatorial optimization

91B26: Auctions, bargaining, bidding and selling, and other market models

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