Hardness Results for the Power Range Assignment Problem in Packet Radio Networks View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999

AUTHORS

Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri

ABSTRACT

As for the 3-dimensional case, we strengthen their negative result by showing that the minimum range assignment problem is APX-complete, so, it does not admit a polynomial-time approximation scheme unless P=NP.

PAGES

197-208

References to SciGraph publications

Book

TITLE

Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-540-66329-4
978-3-540-48413-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-48413-4_21

DOI

http://dx.doi.org/10.1007/978-3-540-48413-4_21

DIMENSIONS

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


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", 
    "author": [
      {
        "affiliation": {
          "name": [
            "Dipartimento di Matematica, Universit\u00e0 di Roma \u201cTor Vergata\u201d,"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Clementi", 
        "givenName": "Andrea E. F.", 
        "id": "sg:person.011027660123.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Dipartimento di Matematica, Universit\u00e0 di Roma \u201cTor Vergata\u201d,"
          ], 
          "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": {
          "name": [
            "Dipartimento di Matematica Pura e Applicata, Universit\u2018a de L\u2019Aquila,"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Silvestri", 
        "givenName": "Riccardo", 
        "id": "sg:person.012430640403.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-62495-3_44", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000281398", 
          "https://doi.org/10.1007/3-540-62495-3_44"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0023473", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004661921", 
          "https://doi.org/10.1007/bfb0023473"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0023473", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004661921", 
          "https://doi.org/10.1007/bfb0023473"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02086606", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024228802", 
          "https://doi.org/10.1007/bf02086606"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02086606", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024228802", 
          "https://doi.org/10.1007/bf02086606"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/174644.174650", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025317817"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-62592-5_80", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042261594", 
          "https://doi.org/10.1007/3-540-62592-5_80"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(91)90023-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043200457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/26.52656", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061137305"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/90.222924", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061247023"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tc.1981.6312176", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061532644"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/infcom.1989.101493", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086254353"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.21236/ada126696", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091745570"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "As for the 3-dimensional case, we strengthen their negative result by showing that the minimum range assignment problem is APX-complete, so, it does not admit a polynomial-time approximation scheme unless P=NP.", 
    "editor": [
      {
        "familyName": "Hochbaum", 
        "givenName": "Dorit S.", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Sinclair", 
        "givenName": "Alistair", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-48413-4_21", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66329-4", 
        "978-3-540-48413-4"
      ], 
      "name": "Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "name": "Hardness Results for the Power Range Assignment Problem in Packet Radio Networks", 
    "pagination": "197-208", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-48413-4_21"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "2e0b3a3b2652289b401e55b2719bfbf1c309fbb842eb096e5dbec65fb231ee8e"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009665385"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-48413-4_21", 
      "https://app.dimensions.ai/details/publication/pub.1009665385"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T21:00", 
    "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/0000000001_0000000264/records_8690_00000249.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-540-48413-4_21"
  }
]
 

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-48413-4_21'

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-48413-4_21'

Turtle is a human-readable linked data format.

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

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-48413-4_21'


 

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

126 TRIPLES      22 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-48413-4_21 schema:author N885a42d60e9148de857ff09c8d2eba17
2 schema:citation sg:pub.10.1007/3-540-62495-3_44
3 sg:pub.10.1007/3-540-62592-5_80
4 sg:pub.10.1007/bf02086606
5 sg:pub.10.1007/bfb0023473
6 https://doi.org/10.1016/0022-0000(91)90023-x
7 https://doi.org/10.1109/26.52656
8 https://doi.org/10.1109/90.222924
9 https://doi.org/10.1109/infcom.1989.101493
10 https://doi.org/10.1109/tc.1981.6312176
11 https://doi.org/10.1145/174644.174650
12 https://doi.org/10.21236/ada126696
13 schema:datePublished 1999
14 schema:datePublishedReg 1999-01-01
15 schema:description As for the 3-dimensional case, we strengthen their negative result by showing that the minimum range assignment problem is APX-complete, so, it does not admit a polynomial-time approximation scheme unless P=NP.
16 schema:editor Nede9f5bfd359422ea45173e0e3fc6c1c
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf Ne1a98d10994341c2bcea240b81665a7d
21 schema:name Hardness Results for the Power Range Assignment Problem in Packet Radio Networks
22 schema:pagination 197-208
23 schema:productId N4cbb081c40614cb09ca94106ed60d225
24 N5129b590b2144f8baa87e217adbc4db8
25 Needb15d8e8c849378420269e62c86eaa
26 schema:publisher N656135f4c1384fc0b8015666217c3295
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009665385
28 https://doi.org/10.1007/978-3-540-48413-4_21
29 schema:sdDatePublished 2019-04-15T21:00
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher Nf730680e09d5446d9f8a651f50f99945
32 schema:url http://link.springer.com/10.1007/978-3-540-48413-4_21
33 sgo:license sg:explorer/license/
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
36 N07bbdc987f8a44cfab292282920a5a4f schema:familyName Sinclair
37 schema:givenName Alistair
38 rdf:type schema:Person
39 N174869e1590441d6b06689e55731ff1a rdf:first Ne6707aba36d14e51bd7226406e82ed5d
40 rdf:rest N42b6d510b3da444291e6f381397f3e29
41 N1a0548ad64ce405eb344395dfc94eccd rdf:first sg:person.012430640403.64
42 rdf:rest rdf:nil
43 N20e7d4cbf18a4d788df7fc3a5d137a94 schema:name Dipartimento di Matematica Pura e Applicata, Universit‘a de L’Aquila,
44 rdf:type schema:Organization
45 N3c6fdc06c6bf48708e11c93c222c371f rdf:first sg:person.013624103516.76
46 rdf:rest N1a0548ad64ce405eb344395dfc94eccd
47 N42b6d510b3da444291e6f381397f3e29 rdf:first N492d72066bb140c1bf64a7596383e33a
48 rdf:rest Nf769642fbde74423a7713bfd7a6af314
49 N4733112d60a349d789642ef769bea049 schema:familyName Hochbaum
50 schema:givenName Dorit S.
51 rdf:type schema:Person
52 N492d72066bb140c1bf64a7596383e33a schema:familyName Rolim
53 schema:givenName José D. P.
54 rdf:type schema:Person
55 N4cbb081c40614cb09ca94106ed60d225 schema:name readcube_id
56 schema:value 2e0b3a3b2652289b401e55b2719bfbf1c309fbb842eb096e5dbec65fb231ee8e
57 rdf:type schema:PropertyValue
58 N5129b590b2144f8baa87e217adbc4db8 schema:name dimensions_id
59 schema:value pub.1009665385
60 rdf:type schema:PropertyValue
61 N656135f4c1384fc0b8015666217c3295 schema:location Berlin, Heidelberg
62 schema:name Springer Berlin Heidelberg
63 rdf:type schema:Organisation
64 N885a42d60e9148de857ff09c8d2eba17 rdf:first sg:person.011027660123.21
65 rdf:rest N3c6fdc06c6bf48708e11c93c222c371f
66 Nae45bf477e9d453c94dbeea147f37e22 schema:name Dipartimento di Matematica, Università di Roma “Tor Vergata”,
67 rdf:type schema:Organization
68 Ne1a98d10994341c2bcea240b81665a7d schema:isbn 978-3-540-48413-4
69 978-3-540-66329-4
70 schema:name Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques
71 rdf:type schema:Book
72 Ne6707aba36d14e51bd7226406e82ed5d schema:familyName Jansen
73 schema:givenName Klaus
74 rdf:type schema:Person
75 Ne9644bfe2f0849f48c71671eb97120ff schema:name Dipartimento di Matematica, Università di Roma “Tor Vergata”,
76 rdf:type schema:Organization
77 Nede9f5bfd359422ea45173e0e3fc6c1c rdf:first N4733112d60a349d789642ef769bea049
78 rdf:rest N174869e1590441d6b06689e55731ff1a
79 Needb15d8e8c849378420269e62c86eaa schema:name doi
80 schema:value 10.1007/978-3-540-48413-4_21
81 rdf:type schema:PropertyValue
82 Nf730680e09d5446d9f8a651f50f99945 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 Nf769642fbde74423a7713bfd7a6af314 rdf:first N07bbdc987f8a44cfab292282920a5a4f
85 rdf:rest rdf:nil
86 sg:person.011027660123.21 schema:affiliation Ne9644bfe2f0849f48c71671eb97120ff
87 schema:familyName Clementi
88 schema:givenName Andrea E. F.
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21
90 rdf:type schema:Person
91 sg:person.012430640403.64 schema:affiliation N20e7d4cbf18a4d788df7fc3a5d137a94
92 schema:familyName Silvestri
93 schema:givenName Riccardo
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64
95 rdf:type schema:Person
96 sg:person.013624103516.76 schema:affiliation Nae45bf477e9d453c94dbeea147f37e22
97 schema:familyName Penna
98 schema:givenName Paolo
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
100 rdf:type schema:Person
101 sg:pub.10.1007/3-540-62495-3_44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000281398
102 https://doi.org/10.1007/3-540-62495-3_44
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/3-540-62592-5_80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042261594
105 https://doi.org/10.1007/3-540-62592-5_80
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/bf02086606 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024228802
108 https://doi.org/10.1007/bf02086606
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/bfb0023473 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004661921
111 https://doi.org/10.1007/bfb0023473
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/0022-0000(91)90023-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043200457
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1109/26.52656 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061137305
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1109/90.222924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061247023
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1109/infcom.1989.101493 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086254353
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1109/tc.1981.6312176 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532644
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1145/174644.174650 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025317817
124 rdf:type schema:CreativeWork
125 https://doi.org/10.21236/ada126696 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091745570
126 rdf:type schema:CreativeWork
 




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


...