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


...