A simple and fast algorithm for convex decomposition in relax-and-round mechanisms

DOI10.1016/j.cor.2018.11.017zbMath1458.91108OpenAlexW2902520606WikidataQ128898173 ScholiaQ128898173MaRDI QIDQ1634087

Salman Fadaei, Martin Bichler, Dennis Kraft

Publication date: 17 December 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2018.11.017

zbMATH Keywords

linear programmingapproximation algorithmslogisticsalgorithmic mechanism design

Mathematics Subject Classification ID

Linear programming (90C05) Transportation, logistics and supply chain management (90B06) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Towards more practical linear programming-based techniques for algorithmic mechanism design
• Solving multiple scenarios in a combinatorial auction
• Bundling equilibrium in combinatorial auctions
• A new bidding framework for combinatorial e-auctions
• Fast Convex Decomposition for Truthful Social Welfare Approximation
• A Linear-Programming Approximation of AC Power Flows
• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
• Handbook of Spectrum Auction Design
• Approximation of the Quadratic Knapsack Problem
• Randomized metarounding (extended abstract)
• Approximation techniques for utilitarian mechanism design
• Feature Article—The Ellipsoid Method: A Survey
• On the Power of Randomization in Algorithmic Mechanism Design
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Algorithmic Game Theory

This page was built for publication: A simple and fast algorithm for convex decomposition in relax-and-round mechanisms