Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Piotr Berman , Grigory Yaroslavtsev

ABSTRACT

We present primal-dual algorithms which give a 2.4 approximation for a class of node-weighted network design problems in planar graphs, introduced by Demaine, Hajiaghayi and Klein (ICALP’09). This class includes Node-Weighted Steiner Forest problem studied recently by Moldenhauer (ICALP’11) and other node-weighted problems in planar graphs that can be expressed using (0,1)-proper functions introduced by Goemans and Williamson. We show that these problems can be equivalently formulated as feedback vertex set problems and analyze approximation factors guaranteed by different violation oracles within the primal-dual framework developed by Goemans and Williamson. More... »

PAGES

50-60

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-32511-3
978-3-642-32512-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-32512-0_5

DOI

http://dx.doi.org/10.1007/978-3-642-32512-0_5

DIMENSIONS

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


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": "Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University, 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": "Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yaroslavtsev", 
        "givenName": "Grigory", 
        "id": "sg:person.015277345473.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "We present primal-dual algorithms which give a 2.4 approximation for a class of node-weighted network design problems in planar graphs, introduced by Demaine, Hajiaghayi and Klein (ICALP\u201909). This class includes Node-Weighted Steiner Forest problem studied recently by Moldenhauer (ICALP\u201911) and other node-weighted problems in planar graphs that can be expressed using (0,1)-proper functions introduced by Goemans and Williamson. We show that these problems can be equivalently formulated as feedback vertex set problems and analyze approximation factors guaranteed by different violation oracles within the primal-dual framework developed by Goemans and Williamson.", 
    "editor": [
      {
        "familyName": "Gupta", 
        "givenName": "Anupam", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9", 
        "type": "Person"
      }, 
      {
        "familyName": "Servedio", 
        "givenName": "Rocco", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-32512-0_5", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-32511-3", 
        "978-3-642-32512-0"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "planar graphs", 
      "primal-dual framework", 
      "primal-dual algorithm", 
      "network design problem", 
      "Dual Approximation Algorithm", 
      "Steiner forest problem", 
      "feedback vertex", 
      "approximation algorithm", 
      "design problem", 
      "approximation factor", 
      "network design", 
      "Goemans", 
      "graph", 
      "forest problem", 
      "problem", 
      "algorithm", 
      "approximation", 
      "Hajiaghayi", 
      "class", 
      "Demaine", 
      "vertices", 
      "Klein", 
      "Williamson", 
      "oracle", 
      "framework", 
      "function", 
      "design", 
      "proper function", 
      "factors"
    ], 
    "name": "Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs", 
    "pagination": "50-60", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015462454"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-32512-0_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-32512-0_5", 
      "https://app.dimensions.ai/details/publication/pub.1015462454"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:21", 
    "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_453.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-32512-0_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/978-3-642-32512-0_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/978-3-642-32512-0_5'

Turtle is a human-readable linked data format.

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

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-32512-0_5'


 

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

110 TRIPLES      22 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-32512-0_5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nea92fba0a0934d8f814328ff20681c27
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description We present primal-dual algorithms which give a 2.4 approximation for a class of node-weighted network design problems in planar graphs, introduced by Demaine, Hajiaghayi and Klein (ICALP’09). This class includes Node-Weighted Steiner Forest problem studied recently by Moldenhauer (ICALP’11) and other node-weighted problems in planar graphs that can be expressed using (0,1)-proper functions introduced by Goemans and Williamson. We show that these problems can be equivalently formulated as feedback vertex set problems and analyze approximation factors guaranteed by different violation oracles within the primal-dual framework developed by Goemans and Williamson.
7 schema:editor Nf8b734e30bd74404aebe14d21d4b4fbe
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nd3756173dcaf4a838d9041b2a3102ba8
11 schema:keywords Demaine
12 Dual Approximation Algorithm
13 Goemans
14 Hajiaghayi
15 Klein
16 Steiner forest problem
17 Williamson
18 algorithm
19 approximation
20 approximation algorithm
21 approximation factor
22 class
23 design
24 design problem
25 factors
26 feedback vertex
27 forest problem
28 framework
29 function
30 graph
31 network design
32 network design problem
33 oracle
34 planar graphs
35 primal-dual algorithm
36 primal-dual framework
37 problem
38 proper function
39 vertices
40 schema:name Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs
41 schema:pagination 50-60
42 schema:productId N676234d4640b44e59746972c103d9754
43 N77819e7b335e460880a0f1a431731c8f
44 schema:publisher N1ac821114d6f4cff88aff7d1ef8acf08
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015462454
46 https://doi.org/10.1007/978-3-642-32512-0_5
47 schema:sdDatePublished 2022-08-04T17:21
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N82c8a72540904bb2b3b88054b0121951
50 schema:url https://doi.org/10.1007/978-3-642-32512-0_5
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N1ac821114d6f4cff88aff7d1ef8acf08 schema:name Springer Nature
55 rdf:type schema:Organisation
56 N1bac72e881134a76a917649d05ac9d44 rdf:first N6bd9657b479142bd9d73f432602ba7c5
57 rdf:rest rdf:nil
58 N20949453219c438b8ff2b83139adc640 rdf:first N65cb64c1f9154b55aba3adcfb4258d06
59 rdf:rest Nf851f329cc2744c888027c83ca75c0de
60 N65cb64c1f9154b55aba3adcfb4258d06 schema:familyName Jansen
61 schema:givenName Klaus
62 rdf:type schema:Person
63 N676234d4640b44e59746972c103d9754 schema:name doi
64 schema:value 10.1007/978-3-642-32512-0_5
65 rdf:type schema:PropertyValue
66 N6bd9657b479142bd9d73f432602ba7c5 schema:familyName Servedio
67 schema:givenName Rocco
68 rdf:type schema:Person
69 N73b4070cc9a245d3b51926dfdf5ed22a schema:familyName Rolim
70 schema:givenName José
71 rdf:type schema:Person
72 N77819e7b335e460880a0f1a431731c8f schema:name dimensions_id
73 schema:value pub.1015462454
74 rdf:type schema:PropertyValue
75 N82c8a72540904bb2b3b88054b0121951 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N856004e28b3b4cc0869bcb456b455b20 schema:familyName Gupta
78 schema:givenName Anupam
79 rdf:type schema:Person
80 Nb0c7460aacc948e4bd48ff41d30707e7 rdf:first sg:person.015277345473.26
81 rdf:rest rdf:nil
82 Nd3756173dcaf4a838d9041b2a3102ba8 schema:isbn 978-3-642-32511-3
83 978-3-642-32512-0
84 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
85 rdf:type schema:Book
86 Nea92fba0a0934d8f814328ff20681c27 rdf:first sg:person.01274506210.27
87 rdf:rest Nb0c7460aacc948e4bd48ff41d30707e7
88 Nf851f329cc2744c888027c83ca75c0de rdf:first N73b4070cc9a245d3b51926dfdf5ed22a
89 rdf:rest N1bac72e881134a76a917649d05ac9d44
90 Nf8b734e30bd74404aebe14d21d4b4fbe rdf:first N856004e28b3b4cc0869bcb456b455b20
91 rdf:rest N20949453219c438b8ff2b83139adc640
92 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
93 schema:name Information and Computing Sciences
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
96 schema:name Computation Theory and Mathematics
97 rdf:type schema:DefinedTerm
98 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
99 schema:familyName Berman
100 schema:givenName Piotr
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
102 rdf:type schema:Person
103 sg:person.015277345473.26 schema:affiliation grid-institutes:grid.29857.31
104 schema:familyName Yaroslavtsev
105 schema:givenName Grigory
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26
107 rdf:type schema:Person
108 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University, USA
109 schema:name Pennsylvania State University, USA
110 rdf:type schema:Organization
 




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


...