Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  A Truthful Constant Approximation for Maximizing the Minimum Load on Related Machines

Christodoulou, G., Kovacs, A., & van Stee, R. (2010). A Truthful Constant Approximation for Maximizing the Minimum Load on Related Machines. In A. Saberi (Ed.), Internet and Network Economics (pp. 182-193). Berlin: Springer. doi:10.1007/978-3-642-17572-5_15.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1613-F Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-285D-8
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Christodoulou, George1, Autor           
Kovacs, Annamaria1, Autor           
van Stee, Rob1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Designing truthful mechanisms for scheduling on related machines is a very important problem in single-parameter mechanism design. We consider the covering objective, that is we are interested in maximizing the minimum completion time of a machine. This problem falls into the class of problems where the optimal allocation can be truthfully implemented. A major open issue for this class is whether truthfulness affects the polynomial-time implementation. We provide the first constant factor approxi\-mation for deterministic truthful mechanisms. In particular we come up with a $2+\eps$ approximation guarantee, significantly improving on the previous upper bound of $\min(m,(2+\eps)s_m/s_1)$.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20102010
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 536688
DOI: 10.1007/978-3-642-17572-5_15
Anderer: Local-ID: C1256428004B93B8-0F8E6D7392675EDAC12577F400520301-ChKoSt10
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 6th International Workshop on Internet and Network Economics
Veranstaltungsort: Stanford, USA
Start-/Enddatum: 2010-12-13 - 2010-12-17

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Internet and Network Economics
  Untertitel : 6th International Workshop, WINE 2010
  Kurztitel : WINE 2010
Genre der Quelle: Konferenzband
 Urheber:
Saberi, Amin1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 182 - 193 Identifikator: ISBN: 978-3-642-17571-8

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 6484 Artikelnummer: - Start- / Endseite: - Identifikator: -