English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. Item Summary / 
  2. View item

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-490A-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0026-A2CF-0
Genre: Paper

Files

show Files
hide Files
:
arXiv:1408.1577.pdf (Preprint), 304KB
View   Save
File Permalink:
https://hdl.handle.net/11858/00-001M-0000-0024-490C-7
Name:
arXiv:1408.1577.pdf
Description:
File downloaded from arXiv at 2014-12-03 14:42
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
http://arxiv.org/help/license

Locators

show

Creators

show
hide
 Creators:
Elbassioni, Khaled1, Author           
Mehlhorn, Kurt1, Author           
Ramezani, Fahimeh1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Data Structures and Algorithms, cs.DS
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2014-08-072014-08-07
 Publication Status: Published online
 Pages: 22 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1408.1577
URI: http://arxiv.org/abs/1408.1577
BibTex Citekey: DBLP:journals/corr/ElbassioniMR14
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show