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 N6e33a478b5c940f4b6313695b548b9d2
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 N15053d31420846fda7e087f9fc422333
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf N6165d1daea984dd4bb7cd3ec715ec822
21 schema:name Hardness Results for the Power Range Assignment Problem in Packet Radio Networks
22 schema:pagination 197-208
23 schema:productId N41a6bf9179f640aebb292e09c1a9419b
24 N72a3bf2618fb453984348bb2ea2da7b6
25 Nc42abbf848204de78801dc7044ff1005
26 schema:publisher Nd6f59960851647e69bec184a21b79703
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 N390fbfa5ab974c58a5ba9267e0091247
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 N0c8f13411f3d490dbb31fd31d8e4aa26 rdf:first sg:person.012430640403.64
37 rdf:rest rdf:nil
38 N15053d31420846fda7e087f9fc422333 rdf:first N88b929cd1bbb4db685bcfac0e2e9960e
39 rdf:rest N9042e62411f94322b498e44025717f58
40 N1b29fb6ece664976ab8a5e1e48adcc3a rdf:first N7ad7a9caad6246eab1410d3c6c3f2e95
41 rdf:rest Nfa54be21b96a482e9fe19cb3e5a41b9b
42 N2d22a09fe9b34def8d6c9a4f768b8190 schema:familyName Jansen
43 schema:givenName Klaus
44 rdf:type schema:Person
45 N2d4a829a0bd64a08a663f3781b8df152 schema:name Dipartimento di Matematica, Università di Roma “Tor Vergata”,
46 rdf:type schema:Organization
47 N2f8e340e0b2a421babcdda482ba5cbd4 schema:familyName Sinclair
48 schema:givenName Alistair
49 rdf:type schema:Person
50 N390fbfa5ab974c58a5ba9267e0091247 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N41a6bf9179f640aebb292e09c1a9419b schema:name doi
53 schema:value 10.1007/978-3-540-48413-4_21
54 rdf:type schema:PropertyValue
55 N6165d1daea984dd4bb7cd3ec715ec822 schema:isbn 978-3-540-48413-4
56 978-3-540-66329-4
57 schema:name Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques
58 rdf:type schema:Book
59 N6e33a478b5c940f4b6313695b548b9d2 rdf:first sg:person.011027660123.21
60 rdf:rest Nce67a3b54c9c469a9a82a1dd7cdd3a40
61 N72a3bf2618fb453984348bb2ea2da7b6 schema:name dimensions_id
62 schema:value pub.1009665385
63 rdf:type schema:PropertyValue
64 N7ad7a9caad6246eab1410d3c6c3f2e95 schema:familyName Rolim
65 schema:givenName José D. P.
66 rdf:type schema:Person
67 N88b929cd1bbb4db685bcfac0e2e9960e schema:familyName Hochbaum
68 schema:givenName Dorit S.
69 rdf:type schema:Person
70 N8d81a97754be439fb87fd5890cdf2b76 schema:name Dipartimento di Matematica, Università di Roma “Tor Vergata”,
71 rdf:type schema:Organization
72 N9042e62411f94322b498e44025717f58 rdf:first N2d22a09fe9b34def8d6c9a4f768b8190
73 rdf:rest N1b29fb6ece664976ab8a5e1e48adcc3a
74 N9970b4154b444bc7a7bbfbd97f6041a1 schema:name Dipartimento di Matematica Pura e Applicata, Universit‘a de L’Aquila,
75 rdf:type schema:Organization
76 Nc42abbf848204de78801dc7044ff1005 schema:name readcube_id
77 schema:value 2e0b3a3b2652289b401e55b2719bfbf1c309fbb842eb096e5dbec65fb231ee8e
78 rdf:type schema:PropertyValue
79 Nce67a3b54c9c469a9a82a1dd7cdd3a40 rdf:first sg:person.013624103516.76
80 rdf:rest N0c8f13411f3d490dbb31fd31d8e4aa26
81 Nd6f59960851647e69bec184a21b79703 schema:location Berlin, Heidelberg
82 schema:name Springer Berlin Heidelberg
83 rdf:type schema:Organisation
84 Nfa54be21b96a482e9fe19cb3e5a41b9b rdf:first N2f8e340e0b2a421babcdda482ba5cbd4
85 rdf:rest rdf:nil
86 sg:person.011027660123.21 schema:affiliation N8d81a97754be439fb87fd5890cdf2b76
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 N9970b4154b444bc7a7bbfbd97f6041a1
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 N2d4a829a0bd64a08a663f3781b8df152
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)


...