Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Vincenzo Auletta , Roberto De Prisco , Paolo Penna , Giuseppe Persiano

ABSTRACT

We consider the problem of scheduling jobs on related machines owned by selfish agents and provide the first deterministic mechanisms with constant approximation that are truthful; that is, truth-telling is a dominant strategy for all agents. More precisely, we present deterministic polynomial-time (2+ε)-approximation algorithms and suitable payment functions that yield truthful mechanisms for several NP-hard restrictions of this problem. Our result also yields a family of deterministic polynomial-time truthful (4+ε)-approximation mechanisms for any fixed number of machines. The only previously-known mechanism for this problem (proposed by Archer and Tardos [FOCS 2001]) is 3-approximated, randomized and truthful under a weaker notion of truthfulness. Up to our knowledge, our mechanisms are the first non-trivial polynomial-time deterministic truthful mechanisms for this NP-hard problem. To obtain our results we introduce a technique to transform the PTAS by Graham into a deterministic truthful mechanism. More... »

PAGES

608-619

References to SciGraph publications

Book

TITLE

STACS 2004

ISBN

978-3-540-21236-2
978-3-540-24749-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_53

DOI

http://dx.doi.org/10.1007/978-3-540-24749-4_53

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1025679830


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni \u201cR.M. Capocelli\u201d, Universit\u00e0 di Salerno, via S. Allende 2, I-84081, Baronissi (SA), Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Auletta", 
        "givenName": "Vincenzo", 
        "id": "sg:person.016327521101.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016327521101.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni \u201cR.M. Capocelli\u201d, Universit\u00e0 di Salerno, via S. Allende 2, I-84081, Baronissi (SA), Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "De Prisco", 
        "givenName": "Roberto", 
        "id": "sg:person.015154042177.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015154042177.95"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni \u201cR.M. Capocelli\u201d, Universit\u00e0 di Salerno, via S. Allende 2, I-84081, Baronissi (SA), Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Penna", 
        "givenName": "Paolo", 
        "id": "sg:person.013624103516.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Salerno", 
          "id": "https://www.grid.ac/institutes/grid.11780.3f", 
          "name": [
            "Dipartimento di Informatica ed Applicazioni \u201cR.M. Capocelli\u201d, Universit\u00e0 di Salerno, via S. Allende 2, I-84081, Baronissi (SA), Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Persiano", 
        "givenName": "Giuseppe", 
        "id": "sg:person.013255374317.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013255374317.27"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01726210", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003499590", 
          "https://doi.org/10.1007/bf01726210"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01726210", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003499590", 
          "https://doi.org/10.1007/bf01726210"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/j.1538-7305.1966.tb01709.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017133205"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/380752.380883", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018290072"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/15427951.2004.10129086", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026661626"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1111/j.1540-6261.1961.tb02789.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043120435"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/1914085", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069641186"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2001.959924", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093632931"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2001.959924", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093632931"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2001.959924", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093632931"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/352871.352898", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098948611"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "We consider the problem of scheduling jobs on related machines owned by selfish agents and provide the first deterministic mechanisms with constant approximation that are truthful; that is, truth-telling is a dominant strategy for all agents. More precisely, we present deterministic polynomial-time (2+\u03b5)-approximation algorithms and suitable payment functions that yield truthful mechanisms for several NP-hard restrictions of this problem. Our result also yields a family of deterministic polynomial-time truthful (4+\u03b5)-approximation mechanisms for any fixed number of machines. The only previously-known mechanism for this problem (proposed by Archer and Tardos [FOCS 2001]) is 3-approximated, randomized and truthful under a weaker notion of truthfulness. Up to our knowledge, our mechanisms are the first non-trivial polynomial-time deterministic truthful mechanisms for this NP-hard problem. To obtain our results we introduce a technique to transform the PTAS by Graham into a deterministic truthful mechanism.", 
    "editor": [
      {
        "familyName": "Diekert", 
        "givenName": "Volker", 
        "type": "Person"
      }, 
      {
        "familyName": "Habib", 
        "givenName": "Michel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24749-4_53", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-21236-2", 
        "978-3-540-24749-4"
      ], 
      "name": "STACS 2004", 
      "type": "Book"
    }, 
    "name": "Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines", 
    "pagination": "608-619", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025679830"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24749-4_53"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "7a56ff5df616017a741e9edf22bd601e624c6c8e5a0c31ff7a81c5aaa3ccb6d1"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24749-4_53", 
      "https://app.dimensions.ai/details/publication/pub.1025679830"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:28", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70066_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-24749-4_53"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_53'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_53'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_53'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24749-4_53'


 

This table displays all metadata directly associated to this object as RDF triples.

116 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24749-4_53 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N2efdb5cd231a469890eb1c650aaa9fa6
4 schema:citation sg:pub.10.1007/bf01726210
5 https://doi.org/10.1002/j.1538-7305.1966.tb01709.x
6 https://doi.org/10.1080/15427951.2004.10129086
7 https://doi.org/10.1109/sfcs.2001.959924
8 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x
9 https://doi.org/10.1145/352871.352898
10 https://doi.org/10.1145/380752.380883
11 https://doi.org/10.2307/1914085
12 schema:datePublished 2004
13 schema:datePublishedReg 2004-01-01
14 schema:description We consider the problem of scheduling jobs on related machines owned by selfish agents and provide the first deterministic mechanisms with constant approximation that are truthful; that is, truth-telling is a dominant strategy for all agents. More precisely, we present deterministic polynomial-time (2+ε)-approximation algorithms and suitable payment functions that yield truthful mechanisms for several NP-hard restrictions of this problem. Our result also yields a family of deterministic polynomial-time truthful (4+ε)-approximation mechanisms for any fixed number of machines. The only previously-known mechanism for this problem (proposed by Archer and Tardos [FOCS 2001]) is 3-approximated, randomized and truthful under a weaker notion of truthfulness. Up to our knowledge, our mechanisms are the first non-trivial polynomial-time deterministic truthful mechanisms for this NP-hard problem. To obtain our results we introduce a technique to transform the PTAS by Graham into a deterministic truthful mechanism.
15 schema:editor N1ae79648461b491498186adbe4d1bcbb
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf Nc30f9eb015904c9293547b0040d3a5ce
20 schema:name Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines
21 schema:pagination 608-619
22 schema:productId N0bfd2f6c90be41c5886f3cad4370981d
23 N6fc55ae927564104992c9f393fc96ae8
24 Ncbe1554dc1484fc8881a2a461b2c8593
25 schema:publisher Nd6a9e3998de7435bb24d1237d7dcf967
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025679830
27 https://doi.org/10.1007/978-3-540-24749-4_53
28 schema:sdDatePublished 2019-04-16T08:28
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N85b71a303bca42f4bfd56e995138a6e3
31 schema:url https://link.springer.com/10.1007%2F978-3-540-24749-4_53
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N0bfd2f6c90be41c5886f3cad4370981d schema:name readcube_id
36 schema:value 7a56ff5df616017a741e9edf22bd601e624c6c8e5a0c31ff7a81c5aaa3ccb6d1
37 rdf:type schema:PropertyValue
38 N1ae79648461b491498186adbe4d1bcbb rdf:first N9deafd6af8c54f01ac763f62296ec659
39 rdf:rest N9606b5f632054194a6009e2b849d2e2a
40 N2efdb5cd231a469890eb1c650aaa9fa6 rdf:first sg:person.016327521101.60
41 rdf:rest N7ca0ccfa321b4377a9928a950482af19
42 N30f1d8bc1d4c4531878582eba9046f2a rdf:first sg:person.013255374317.27
43 rdf:rest rdf:nil
44 N6fc55ae927564104992c9f393fc96ae8 schema:name doi
45 schema:value 10.1007/978-3-540-24749-4_53
46 rdf:type schema:PropertyValue
47 N7ca0ccfa321b4377a9928a950482af19 rdf:first sg:person.015154042177.95
48 rdf:rest Nb4c615b0ce4d48959a96dabca2eb2e5c
49 N85b71a303bca42f4bfd56e995138a6e3 schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 N8b0c523712a14f8fad400d7b518ce97d schema:familyName Habib
52 schema:givenName Michel
53 rdf:type schema:Person
54 N9606b5f632054194a6009e2b849d2e2a rdf:first N8b0c523712a14f8fad400d7b518ce97d
55 rdf:rest rdf:nil
56 N9deafd6af8c54f01ac763f62296ec659 schema:familyName Diekert
57 schema:givenName Volker
58 rdf:type schema:Person
59 Nb4c615b0ce4d48959a96dabca2eb2e5c rdf:first sg:person.013624103516.76
60 rdf:rest N30f1d8bc1d4c4531878582eba9046f2a
61 Nc30f9eb015904c9293547b0040d3a5ce schema:isbn 978-3-540-21236-2
62 978-3-540-24749-4
63 schema:name STACS 2004
64 rdf:type schema:Book
65 Ncbe1554dc1484fc8881a2a461b2c8593 schema:name dimensions_id
66 schema:value pub.1025679830
67 rdf:type schema:PropertyValue
68 Nd6a9e3998de7435bb24d1237d7dcf967 schema:location Berlin, Heidelberg
69 schema:name Springer Berlin Heidelberg
70 rdf:type schema:Organisation
71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
72 schema:name Information and Computing Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
75 schema:name Computation Theory and Mathematics
76 rdf:type schema:DefinedTerm
77 sg:person.013255374317.27 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
78 schema:familyName Persiano
79 schema:givenName Giuseppe
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013255374317.27
81 rdf:type schema:Person
82 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
83 schema:familyName Penna
84 schema:givenName Paolo
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
86 rdf:type schema:Person
87 sg:person.015154042177.95 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
88 schema:familyName De Prisco
89 schema:givenName Roberto
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015154042177.95
91 rdf:type schema:Person
92 sg:person.016327521101.60 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
93 schema:familyName Auletta
94 schema:givenName Vincenzo
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016327521101.60
96 rdf:type schema:Person
97 sg:pub.10.1007/bf01726210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003499590
98 https://doi.org/10.1007/bf01726210
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1002/j.1538-7305.1966.tb01709.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1017133205
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1080/15427951.2004.10129086 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026661626
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1109/sfcs.2001.959924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093632931
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1111/j.1540-6261.1961.tb02789.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043120435
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1145/352871.352898 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098948611
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1145/380752.380883 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018290072
111 rdf:type schema:CreativeWork
112 https://doi.org/10.2307/1914085 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069641186
113 rdf:type schema:CreativeWork
114 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
115 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, I-84081, Baronissi (SA), Italy
116 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...