日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細


公開

成果報告書

Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design

MPS-Authors
/persons/resource/persons44374

Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45252

Ramezani,  Fahimeh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
There are no locators available
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
フルテキスト (公開)

arXiv:1408.1577.pdf
(プレプリント), 304KB

付随資料 (公開)
There is no public supplementary material available
引用

Elbassioni, K., Mehlhorn, K., & Ramezani, F. (2014). Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design. Retrieved from http://arxiv.org/abs/1408.1577.


引用: https://hdl.handle.net/11858/00-001M-0000-0024-490A-B
要旨
R. Lavy and C. Swamy (FOCS 2005, J. ACM 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees.