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


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2011-11-16

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.In particular, 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. This substantially improves on the best known approximation ratio for the latter antenna problem equal to 3.Furthermore, we provide a PTAS for the dual problem where the number of sets (e.g., antennas) to use is fixed and the task is to minimize the maximum set load, in case the sets correspond to line intervals or arcs.Finally, we discuss the approximability of the generalization of the antenna problem to include several base stations for antennas, and in particular show its APX-hardness already in the uncapacitated case. More... »

PAGES

295-310

References to SciGraph publications

  • 1995-12-01. Almost optimal set covers in finite VC-dimension in DISCRETE & COMPUTATIONAL GEOMETRY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-011-9591-5

    DOI

    http://dx.doi.org/10.1007/s00453-011-9591-5

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Engineering, Pennsylvania State University, University Park, USA", 
              "id": "http://www.grid.ac/institutes/grid.29857.31", 
              "name": [
                "Department of Computer Science and Engineering, Pennsylvania State University, University Park, USA"
              ], 
              "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, Bonn, Germany", 
              "id": "http://www.grid.ac/institutes/grid.10388.32", 
              "name": [
                "Department of Computer Science, University of Bonn, Bonn, Germany"
              ], 
              "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, Lund, Sweden", 
              "id": "http://www.grid.ac/institutes/grid.4514.4", 
              "name": [
                "Department of Computer Science, Lund University, Lund, Sweden"
              ], 
              "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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02570718", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004339164", 
              "https://doi.org/10.1007/bf02570718"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2011-11-16", 
        "datePublishedReg": "2011-11-16", 
        "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.In particular, 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\u00a02.357. This substantially improves on the best known approximation ratio for the latter antenna problem equal to\u00a03.Furthermore, we provide a PTAS for the dual problem where the number of sets (e.g., antennas) to use is fixed and the task is to minimize the maximum set load, in case the sets correspond to line intervals or arcs.Finally, we discuss the approximability of the generalization of the antenna problem to include several base stations for antennas, and in particular show its APX-hardness already in the uncapacitated case.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00453-011-9591-5", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "64"
          }
        ], 
        "keywords": [
          "approximation algorithm", 
          "antenna problems", 
          "cover problem", 
          "set cover problem", 
          "polynomial-time approximation algorithm", 
          "variable angular range", 
          "known approximation ratio", 
          "exact solution", 
          "dual problem", 
          "family of sets", 
          "polynomial time algorithm", 
          "geometric variants", 
          "approximation ratio", 
          "n points", 
          "set cover", 
          "uncapacitated case", 
          "number of sets", 
          "line interval", 
          "minimum number", 
          "uncapacitated version", 
          "real weight", 
          "base station", 
          "angular range", 
          "directional antennas", 
          "algorithm", 
          "problem", 
          "antenna", 
          "set of elements", 
          "ratio R", 
          "set", 
          "approximability", 
          "generalization", 
          "set load", 
          "geometric", 
          "set of customers", 
          "version", 
          "sum", 
          "solution", 
          "number", 
          "elements", 
          "cases", 
          "deadlines", 
          "assignment", 
          "stations", 
          "arc", 
          "subset", 
          "ratio", 
          "results", 
          "interval", 
          "range", 
          "family", 
          "task", 
          "variants", 
          "load", 
          "goal", 
          "weight", 
          "PTA", 
          "customers", 
          "capacity", 
          "composition", 
          "cover"
        ], 
        "name": "Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems", 
        "pagination": "295-310", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1045578733"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-011-9591-5"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-011-9591-5", 
          "https://app.dimensions.ai/details/publication/pub.1045578733"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-08-04T17:00", 
        "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/article/article_542.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00453-011-9591-5"
      }
    ]
     

    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/s00453-011-9591-5'

    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/s00453-011-9591-5'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-011-9591-5'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-011-9591-5'


     

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

    142 TRIPLES      21 PREDICATES      86 URIs      77 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-011-9591-5 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N290db3d883d940b48ff328378543c864
    4 schema:citation sg:pub.10.1007/bf02570718
    5 schema:datePublished 2011-11-16
    6 schema:datePublishedReg 2011-11-16
    7 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.In particular, 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. This substantially improves on the best known approximation ratio for the latter antenna problem equal to 3.Furthermore, we provide a PTAS for the dual problem where the number of sets (e.g., antennas) to use is fixed and the task is to minimize the maximum set load, in case the sets correspond to line intervals or arcs.Finally, we discuss the approximability of the generalization of the antenna problem to include several base stations for antennas, and in particular show its APX-hardness already in the uncapacitated case.
    8 schema:genre article
    9 schema:isAccessibleForFree false
    10 schema:isPartOf N47c5fdd2013a4cd08afa50062c8cdab7
    11 Nc0707205911e490fba2a9820a287e9a3
    12 sg:journal.1047644
    13 schema:keywords PTA
    14 algorithm
    15 angular range
    16 antenna
    17 antenna problems
    18 approximability
    19 approximation algorithm
    20 approximation ratio
    21 arc
    22 assignment
    23 base station
    24 capacity
    25 cases
    26 composition
    27 cover
    28 cover problem
    29 customers
    30 deadlines
    31 directional antennas
    32 dual problem
    33 elements
    34 exact solution
    35 family
    36 family of sets
    37 generalization
    38 geometric
    39 geometric variants
    40 goal
    41 interval
    42 known approximation ratio
    43 line interval
    44 load
    45 minimum number
    46 n points
    47 number
    48 number of sets
    49 polynomial time algorithm
    50 polynomial-time approximation algorithm
    51 problem
    52 range
    53 ratio
    54 ratio R
    55 real weight
    56 results
    57 set
    58 set cover
    59 set cover problem
    60 set load
    61 set of customers
    62 set of elements
    63 solution
    64 stations
    65 subset
    66 sum
    67 task
    68 uncapacitated case
    69 uncapacitated version
    70 variable angular range
    71 variants
    72 version
    73 weight
    74 schema:name Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems
    75 schema:pagination 295-310
    76 schema:productId N26ce7a1e930b4b5c8c60a049e5d6eebc
    77 Nc52d8be992c047b390d316b1fff95dde
    78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045578733
    79 https://doi.org/10.1007/s00453-011-9591-5
    80 schema:sdDatePublished 2022-08-04T17:00
    81 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    82 schema:sdPublisher N7889175558954662a8550f06240c3f06
    83 schema:url https://doi.org/10.1007/s00453-011-9591-5
    84 sgo:license sg:explorer/license/
    85 sgo:sdDataset articles
    86 rdf:type schema:ScholarlyArticle
    87 N1c8467e98bb3495d82b8cd119b3bea01 rdf:first sg:person.011636042271.02
    88 rdf:rest N9b76e6194aca4c13a38b57cf2cd80ad3
    89 N26ce7a1e930b4b5c8c60a049e5d6eebc schema:name doi
    90 schema:value 10.1007/s00453-011-9591-5
    91 rdf:type schema:PropertyValue
    92 N290db3d883d940b48ff328378543c864 rdf:first sg:person.01274506210.27
    93 rdf:rest N1c8467e98bb3495d82b8cd119b3bea01
    94 N47c5fdd2013a4cd08afa50062c8cdab7 schema:issueNumber 2
    95 rdf:type schema:PublicationIssue
    96 N7889175558954662a8550f06240c3f06 schema:name Springer Nature - SN SciGraph project
    97 rdf:type schema:Organization
    98 N9b76e6194aca4c13a38b57cf2cd80ad3 rdf:first sg:person.011645606663.84
    99 rdf:rest rdf:nil
    100 Nc0707205911e490fba2a9820a287e9a3 schema:volumeNumber 64
    101 rdf:type schema:PublicationVolume
    102 Nc52d8be992c047b390d316b1fff95dde schema:name dimensions_id
    103 schema:value pub.1045578733
    104 rdf:type schema:PropertyValue
    105 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    106 schema:name Mathematical Sciences
    107 rdf:type schema:DefinedTerm
    108 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    109 schema:name Pure Mathematics
    110 rdf:type schema:DefinedTerm
    111 sg:journal.1047644 schema:issn 0178-4617
    112 1432-0541
    113 schema:name Algorithmica
    114 schema:publisher Springer Nature
    115 rdf:type schema:Periodical
    116 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
    117 schema:familyName Karpinski
    118 schema:givenName Marek
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
    120 rdf:type schema:Person
    121 sg:person.011645606663.84 schema:affiliation grid-institutes:grid.4514.4
    122 schema:familyName Lingas
    123 schema:givenName Andrzej
    124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011645606663.84
    125 rdf:type schema:Person
    126 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
    127 schema:familyName Berman
    128 schema:givenName Piotr
    129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
    130 rdf:type schema:Person
    131 sg:pub.10.1007/bf02570718 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004339164
    132 https://doi.org/10.1007/bf02570718
    133 rdf:type schema:CreativeWork
    134 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn, Bonn, Germany
    135 schema:name Department of Computer Science, University of Bonn, Bonn, Germany
    136 rdf:type schema:Organization
    137 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University, University Park, USA
    138 schema:name Department of Computer Science and Engineering, Pennsylvania State University, University Park, USA
    139 rdf:type schema:Organization
    140 grid-institutes:grid.4514.4 schema:alternateName Department of Computer Science, Lund University, Lund, Sweden
    141 schema:name Department of Computer Science, Lund University, Lund, Sweden
    142 rdf:type schema:Organization
     




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


    ...