Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Piotr Berman , Marek Karpinski , Andrzej Lingas

ABSTRACT

First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions.Next, we consider the following general (non-necessarily geometric) capacitated set cover problem. There is given a set of elements with real weights and a family of sets of the elements. One can use a set if it is a subset of one of the sets in the family and the sum of the weights of its elements is at most one. The goal is to cover all the elements with the allowed sets.We show that any polynomial-time algorithm that approximates the uncapacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r + 1.357.The composition of these two results yields a polynomial-time approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio 2.357. More... »

PAGES

226-234

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14031-0_26

DOI

http://dx.doi.org/10.1007/978-3-642-14031-0_26

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, Pennsylvania State University", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, Pennsylvania State University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Bonn", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Department of Computer Science, University of Bonn"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Lund University", 
          "id": "http://www.grid.ac/institutes/grid.4514.4", 
          "name": [
            "Department of Computer Science, Lund University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lingas", 
        "givenName": "Andrzej", 
        "id": "sg:person.011645606663.84", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011645606663.84"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions.Next, we consider the following general (non-necessarily geometric) capacitated set cover problem. There is given a set of elements with real weights and a family of sets of the elements. One can use a set if it is a subset of one of the sets in the family and the sum of the weights of its elements is at most one. The goal is to cover all the elements with the allowed sets.We show that any polynomial-time algorithm that approximates the uncapacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r\u2009+\u20091.357.The composition of these two results yields a polynomial-time approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio 2.357.", 
    "editor": [
      {
        "familyName": "Thai", 
        "givenName": "My T.", 
        "type": "Person"
      }, 
      {
        "familyName": "Sahni", 
        "givenName": "Sartaj", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-14031-0_26", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-14030-3", 
        "978-3-642-14031-0"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "approximation algorithm", 
      "cover problem", 
      "set cover problem", 
      "polynomial-time approximation algorithm", 
      "variable angular range", 
      "exact solution", 
      "family of sets", 
      "polynomial time algorithm", 
      "geometric variants", 
      "n points", 
      "set cover", 
      "ratio R", 
      "minimum number", 
      "uncapacitated version", 
      "real weight", 
      "angular range", 
      "directional antennas", 
      "algorithm", 
      "problem", 
      "set of elements", 
      "set", 
      "antenna", 
      "geometric", 
      "set of customers", 
      "version", 
      "sum", 
      "solution", 
      "elements", 
      "number", 
      "deadlines", 
      "assignment", 
      "subset", 
      "results", 
      "range", 
      "family", 
      "variants", 
      "goal", 
      "weight", 
      "customers", 
      "capacity", 
      "composition", 
      "cover"
    ], 
    "name": "Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems", 
    "pagination": "226-234", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004928615"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-14031-0_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-14031-0_26", 
      "https://app.dimensions.ai/details/publication/pub.1004928615"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_186.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-14031-0_26"
  }
]
 

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-642-14031-0_26'

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-642-14031-0_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14031-0_26'

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-642-14031-0_26'


 

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

126 TRIPLES      22 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-14031-0_26 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N2ff7bc1d62614fdb9edc1204aecc1114
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions.Next, we consider the following general (non-necessarily geometric) capacitated set cover problem. There is given a set of elements with real weights and a family of sets of the elements. One can use a set if it is a subset of one of the sets in the family and the sum of the weights of its elements is at most one. The goal is to cover all the elements with the allowed sets.We show that any polynomial-time algorithm that approximates the uncapacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r + 1.357.The composition of these two results yields a polynomial-time approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio 2.357.
7 schema:editor Nb712c4158f4a4e2b80201ae1b0c5d2d3
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N12f74ac1cc384699af4c264ef118b7c2
11 schema:keywords algorithm
12 angular range
13 antenna
14 approximation algorithm
15 assignment
16 capacity
17 composition
18 cover
19 cover problem
20 customers
21 deadlines
22 directional antennas
23 elements
24 exact solution
25 family
26 family of sets
27 geometric
28 geometric variants
29 goal
30 minimum number
31 n points
32 number
33 polynomial time algorithm
34 polynomial-time approximation algorithm
35 problem
36 range
37 ratio R
38 real weight
39 results
40 set
41 set cover
42 set cover problem
43 set of customers
44 set of elements
45 solution
46 subset
47 sum
48 uncapacitated version
49 variable angular range
50 variants
51 version
52 weight
53 schema:name Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems
54 schema:pagination 226-234
55 schema:productId N42d65ad59076481b8661f0fffe3a1bb4
56 N8003d4cd98b54c289d96042c96e3f865
57 schema:publisher Nc940bf43bff642cc9596a8cebe26d4b0
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004928615
59 https://doi.org/10.1007/978-3-642-14031-0_26
60 schema:sdDatePublished 2022-08-04T17:15
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N723035e228eb4cb6a6b3afee8c77de80
63 schema:url https://doi.org/10.1007/978-3-642-14031-0_26
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N12f74ac1cc384699af4c264ef118b7c2 schema:isbn 978-3-642-14030-3
68 978-3-642-14031-0
69 schema:name Computing and Combinatorics
70 rdf:type schema:Book
71 N2ff7bc1d62614fdb9edc1204aecc1114 rdf:first sg:person.01274506210.27
72 rdf:rest Nba327f3d8f2c420d81b8ddfa7b58a565
73 N42d65ad59076481b8661f0fffe3a1bb4 schema:name dimensions_id
74 schema:value pub.1004928615
75 rdf:type schema:PropertyValue
76 N723035e228eb4cb6a6b3afee8c77de80 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N8003d4cd98b54c289d96042c96e3f865 schema:name doi
79 schema:value 10.1007/978-3-642-14031-0_26
80 rdf:type schema:PropertyValue
81 Nb712c4158f4a4e2b80201ae1b0c5d2d3 rdf:first Ne7b29dd4d72444498e959c6d16c36e40
82 rdf:rest Nd0c46494de1f40d4871abee3f16dd0dd
83 Nba327f3d8f2c420d81b8ddfa7b58a565 rdf:first sg:person.011636042271.02
84 rdf:rest Necb4ead8bb174291a149d3ce69d4088a
85 Nc940bf43bff642cc9596a8cebe26d4b0 schema:name Springer Nature
86 rdf:type schema:Organisation
87 Nce912f9ffcf94d2bb4eaa9febe29bf67 schema:familyName Sahni
88 schema:givenName Sartaj
89 rdf:type schema:Person
90 Nd0c46494de1f40d4871abee3f16dd0dd rdf:first Nce912f9ffcf94d2bb4eaa9febe29bf67
91 rdf:rest rdf:nil
92 Ne7b29dd4d72444498e959c6d16c36e40 schema:familyName Thai
93 schema:givenName My T.
94 rdf:type schema:Person
95 Necb4ead8bb174291a149d3ce69d4088a rdf:first sg:person.011645606663.84
96 rdf:rest rdf:nil
97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
98 schema:name Information and Computing Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
101 schema:name Computation Theory and Mathematics
102 rdf:type schema:DefinedTerm
103 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
104 schema:familyName Karpinski
105 schema:givenName Marek
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
107 rdf:type schema:Person
108 sg:person.011645606663.84 schema:affiliation grid-institutes:grid.4514.4
109 schema:familyName Lingas
110 schema:givenName Andrzej
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011645606663.84
112 rdf:type schema:Person
113 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
114 schema:familyName Berman
115 schema:givenName Piotr
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
117 rdf:type schema:Person
118 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn
119 schema:name Department of Computer Science, University of Bonn
120 rdf:type schema:Organization
121 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University
122 schema:name Department of Computer Science and Engineering, Pennsylvania State University
123 rdf:type schema:Organization
124 grid-institutes:grid.4514.4 schema:alternateName Department of Computer Science, Lund University
125 schema:name Department of Computer Science, Lund University
126 rdf:type schema:Organization
 




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


...