On Computing Ad-hoc Selective Families View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001

AUTHORS

Andrea E. F. Clementi , Pilu Crescenzi , Angelo Monti , Paolo Penna , Riccardo Silvestri

ABSTRACT

We study the problem of computing ad-hoc selective families: Given a collection \( \mathcal{F} \) of subsets of [n] = {1,2,...,n}, a selective family for \( \mathcal{F} \) is a collection \( \mathcal{S} \) of subsets of [n] such that for any F ∈ \( \mathcal{F} \) there exists S ∈ \( \mathcal{S} \) such that |F ∩ S|=1. We first provide a polynomial-time algorithm that, for any instance \( \mathcal{F} \) , returns a selective family of size O((1+ log(△ max /△ min )) · log |\( \mathcal{F} \)| ) where ∏max and ∏min denote the maximal and the minimal size of a subset in \( \mathcal{F} \), respectively. This result is applied to the problem of broadcasting in radio networks with known topology. We indeed develop a broadcasting protocol which completes any broadcast operation within O(D log ∏ log n/D) time-slots, where n, D and ∏ denote the number of nodes, the maximal eccentricity, and the maximal in-degree of the network, respectively. Finally, we consider the combinatorial optimization problem of computing broadcasting protocols with minimal completion time and we prove some hardness results regarding the approximability of this problem. More... »

PAGES

211-222

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques

ISBN

978-3-540-42470-3
978-3-540-44666-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44666-4_24

DOI

http://dx.doi.org/10.1007/3-540-44666-4_24

DIMENSIONS

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


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 Rome Tor Vergata", 
          "id": "https://www.grid.ac/institutes/grid.6530.0", 
          "name": [
            "Dipartimento di Matematica, Universit\u00e0 di Roma \u201cTor Vergata\u201d, Italy"
          ], 
          "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": {
          "alternateName": "University of Florence", 
          "id": "https://www.grid.ac/institutes/grid.8404.8", 
          "name": [
            "Dipartimento di Sistemi e Informatica, Universit\u00e0 di Firenze, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Crescenzi", 
        "givenName": "Pilu", 
        "id": "sg:person.07475505355.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07475505355.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Scienze dell\u2019Informazione, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Monti", 
        "givenName": "Angelo", 
        "id": "sg:person.013471123531.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013471123531.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Rome Tor Vergata", 
          "id": "https://www.grid.ac/institutes/grid.6530.0", 
          "name": [
            "Dipartimento di Matematica, Universit\u00e0 di Roma \u201cTor Vergata\u201d, 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": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Scienze dell\u2019Informazione, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Italy"
          ], 
          "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": "https://doi.org/10.1016/0022-0000(91)90015-w", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022812002"
        ], 
        "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.1016/0022-0000(92)90042-h", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044967806"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/26.79285", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061138360"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tcom.1985.1096245", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061554033"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.1985.1057022", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061649139"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001", 
    "datePublishedReg": "2001-01-01", 
    "description": "We study the problem of computing ad-hoc selective families: Given a collection \\( \\mathcal{F} \\) of subsets of [n] = {1,2,...,n}, a selective family for \\( \\mathcal{F} \\) is a collection \\( \\mathcal{S} \\) of subsets of [n] such that for any F \u2208 \\( \\mathcal{F} \\) there exists S \u2208 \\( \\mathcal{S} \\) such that |F \u2229 S|=1. We first provide a polynomial-time algorithm that, for any instance \\( \\mathcal{F} \\) , returns a selective family of size O((1+ log(\u25b3 max /\u25b3 min )) \u00b7 log |\\( \\mathcal{F} \\)| ) where \u220fmax and \u220fmin denote the maximal and the minimal size of a subset in \\( \\mathcal{F} \\), respectively. This result is applied to the problem of broadcasting in radio networks with known topology. We indeed develop a broadcasting protocol which completes any broadcast operation within O(D log \u220f log n/D) time-slots, where n, D and \u220f denote the number of nodes, the maximal eccentricity, and the maximal in-degree of the network, respectively. Finally, we consider the combinatorial optimization problem of computing broadcasting protocols with minimal completion time and we prove some hardness results regarding the approximability of this problem.", 
    "editor": [
      {
        "familyName": "Goemans", 
        "givenName": "Michel", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Trevisan", 
        "givenName": "Luca", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44666-4_24", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42470-3", 
        "978-3-540-44666-8"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques", 
      "type": "Book"
    }, 
    "name": "On Computing Ad-hoc Selective Families", 
    "pagination": "211-222", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44666-4_24"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d9d6cc564949c5317f7848d6409f3d8354789070b1457956b6c50413a62183c7"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045731540"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44666-4_24", 
      "https://app.dimensions.ai/details/publication/pub.1045731540"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T00:51", 
    "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_8700_00000271.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-44666-4_24"
  }
]
 

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/3-540-44666-4_24'

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/3-540-44666-4_24'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44666-4_24'

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

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


 

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

132 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44666-4_24 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N30c05daac5cb497abeb40b581162b017
4 schema:citation https://doi.org/10.1016/0022-0000(91)90015-w
5 https://doi.org/10.1016/0022-0000(91)90023-x
6 https://doi.org/10.1016/0022-0000(92)90042-h
7 https://doi.org/10.1109/26.79285
8 https://doi.org/10.1109/tcom.1985.1096245
9 https://doi.org/10.1109/tit.1985.1057022
10 schema:datePublished 2001
11 schema:datePublishedReg 2001-01-01
12 schema:description We study the problem of computing ad-hoc selective families: Given a collection \( \mathcal{F} \) of subsets of [n] = {1,2,...,n}, a selective family for \( \mathcal{F} \) is a collection \( \mathcal{S} \) of subsets of [n] such that for any F ∈ \( \mathcal{F} \) there exists S ∈ \( \mathcal{S} \) such that |F ∩ S|=1. We first provide a polynomial-time algorithm that, for any instance \( \mathcal{F} \) , returns a selective family of size O((1+ log(△ max /△ min )) · log |\( \mathcal{F} \)| ) where ∏max and ∏min denote the maximal and the minimal size of a subset in \( \mathcal{F} \), respectively. This result is applied to the problem of broadcasting in radio networks with known topology. We indeed develop a broadcasting protocol which completes any broadcast operation within O(D log ∏ log n/D) time-slots, where n, D and ∏ denote the number of nodes, the maximal eccentricity, and the maximal in-degree of the network, respectively. Finally, we consider the combinatorial optimization problem of computing broadcasting protocols with minimal completion time and we prove some hardness results regarding the approximability of this problem.
13 schema:editor N21c60860640340108beadef69e20ae30
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf Nc9e9e0edf6d24c2499f1f37dae845a24
18 schema:name On Computing Ad-hoc Selective Families
19 schema:pagination 211-222
20 schema:productId N1b41176ae6644540a16624990ba81876
21 N284454e25f074a8a95d6e84dd7661cc9
22 Nc9e820d9f19b4860bf9aae7fc44916bd
23 schema:publisher N74bcd2acc6934a8c86af819b5487052c
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045731540
25 https://doi.org/10.1007/3-540-44666-4_24
26 schema:sdDatePublished 2019-04-16T00:51
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher Nd5a7f666563647329c12abca5b53c6eb
29 schema:url http://link.springer.com/10.1007/3-540-44666-4_24
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N065d8ce679884f369c687359806b385a rdf:first sg:person.07475505355.50
34 rdf:rest N53c8a580f7ae4afea5de15aa36995454
35 N16aca3f9e25d4166b260545c7393df05 rdf:first N6bee4be82b45421c9c26a12a5b9e3dbf
36 rdf:rest Na6daf0195bc64fc697954a64eea4f7dc
37 N1b41176ae6644540a16624990ba81876 schema:name dimensions_id
38 schema:value pub.1045731540
39 rdf:type schema:PropertyValue
40 N1de69e970f564658b8b7a173d02294a2 schema:familyName Jansen
41 schema:givenName Klaus
42 rdf:type schema:Person
43 N21c60860640340108beadef69e20ae30 rdf:first N46a29bec916042f08e03028c2db12cc3
44 rdf:rest Na9bb48fa811743fab63f5f107d01036e
45 N284454e25f074a8a95d6e84dd7661cc9 schema:name doi
46 schema:value 10.1007/3-540-44666-4_24
47 rdf:type schema:PropertyValue
48 N30c05daac5cb497abeb40b581162b017 rdf:first sg:person.011027660123.21
49 rdf:rest N065d8ce679884f369c687359806b385a
50 N46a29bec916042f08e03028c2db12cc3 schema:familyName Goemans
51 schema:givenName Michel
52 rdf:type schema:Person
53 N53c8a580f7ae4afea5de15aa36995454 rdf:first sg:person.013471123531.02
54 rdf:rest Ne63c604086114903b20531172227875f
55 N6bee4be82b45421c9c26a12a5b9e3dbf schema:familyName Rolim
56 schema:givenName José D. P.
57 rdf:type schema:Person
58 N74bcd2acc6934a8c86af819b5487052c schema:location Berlin, Heidelberg
59 schema:name Springer Berlin Heidelberg
60 rdf:type schema:Organisation
61 N8c23d64bd59f4fb684ebbef1e88ff2ef schema:familyName Trevisan
62 schema:givenName Luca
63 rdf:type schema:Person
64 Na6daf0195bc64fc697954a64eea4f7dc rdf:first N8c23d64bd59f4fb684ebbef1e88ff2ef
65 rdf:rest rdf:nil
66 Na9bb48fa811743fab63f5f107d01036e rdf:first N1de69e970f564658b8b7a173d02294a2
67 rdf:rest N16aca3f9e25d4166b260545c7393df05
68 Nb0d7425d28244c8eae2eb6bdbe5d9376 rdf:first sg:person.012430640403.64
69 rdf:rest rdf:nil
70 Nc9e820d9f19b4860bf9aae7fc44916bd schema:name readcube_id
71 schema:value d9d6cc564949c5317f7848d6409f3d8354789070b1457956b6c50413a62183c7
72 rdf:type schema:PropertyValue
73 Nc9e9e0edf6d24c2499f1f37dae845a24 schema:isbn 978-3-540-42470-3
74 978-3-540-44666-8
75 schema:name Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques
76 rdf:type schema:Book
77 Nd5a7f666563647329c12abca5b53c6eb schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 Ne63c604086114903b20531172227875f rdf:first sg:person.013624103516.76
80 rdf:rest Nb0d7425d28244c8eae2eb6bdbe5d9376
81 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
82 schema:name Information and Computing Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
85 schema:name Computation Theory and Mathematics
86 rdf:type schema:DefinedTerm
87 sg:person.011027660123.21 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
88 schema:familyName Clementi
89 schema:givenName Andrea E. F.
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21
91 rdf:type schema:Person
92 sg:person.012430640403.64 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
93 schema:familyName Silvestri
94 schema:givenName Riccardo
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64
96 rdf:type schema:Person
97 sg:person.013471123531.02 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
98 schema:familyName Monti
99 schema:givenName Angelo
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013471123531.02
101 rdf:type schema:Person
102 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
103 schema:familyName Penna
104 schema:givenName Paolo
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
106 rdf:type schema:Person
107 sg:person.07475505355.50 schema:affiliation https://www.grid.ac/institutes/grid.8404.8
108 schema:familyName Crescenzi
109 schema:givenName Pilu
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07475505355.50
111 rdf:type schema:Person
112 https://doi.org/10.1016/0022-0000(91)90015-w schema:sameAs https://app.dimensions.ai/details/publication/pub.1022812002
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/0022-0000(91)90023-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043200457
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/0022-0000(92)90042-h schema:sameAs https://app.dimensions.ai/details/publication/pub.1044967806
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/26.79285 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061138360
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1109/tcom.1985.1096245 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061554033
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1109/tit.1985.1057022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061649139
123 rdf:type schema:CreativeWork
124 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
125 schema:name Dipartimento di Matematica, Università di Roma “Tor Vergata”, Italy
126 rdf:type schema:Organization
127 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
128 schema:name Dipartimento di Scienze dell’Informazione, Università di Roma “La Sapienza”, Italy
129 rdf:type schema:Organization
130 https://www.grid.ac/institutes/grid.8404.8 schema:alternateName University of Florence
131 schema:name Dipartimento di Sistemi e Informatica, Università di Firenze, Italy
132 rdf:type schema:Organization
 




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


...