Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Marek Karpinski , Warren Schudy

ABSTRACT

We settle the approximability status of the Minimum Betweenness problem in tournaments by designing a polynomial time approximation scheme (PTAS). No constant factor approximation was previously known. We also introduce a more general class of so-called fragile ranking problems and construct PTASs for them. The results depend on a new technique of dealing with fragile ranking constraints and could be of independent interest. More... »

PAGES

277-288

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-22934-3
978-3-642-22935-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22935-0_24

DOI

http://dx.doi.org/10.1007/978-3-642-22935-0_24

DIMENSIONS

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


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": "Dept. of Computer Science, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of 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": "IBM T.J. Watson Research Center, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J. Watson Research Center, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schudy", 
        "givenName": "Warren", 
        "id": "sg:person.015153430167.81", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015153430167.81"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "We settle the approximability status of the Minimum Betweenness problem in tournaments by designing a polynomial time approximation scheme (PTAS). No constant factor approximation was previously known. We also introduce a more general class of so-called fragile ranking problems and construct PTASs for them. The results depend on a new technique of dealing with fragile ranking constraints and could be of independent interest.", 
    "editor": [
      {
        "familyName": "Goldberg", 
        "givenName": "Leslie Ann", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Ravi", 
        "givenName": "R.", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22935-0_24", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22934-3", 
        "978-3-642-22935-0"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "polynomial time approximation scheme", 
      "approximation scheme", 
      "betweenness problem", 
      "time approximation scheme", 
      "constant factor approximation", 
      "approximability status", 
      "general class", 
      "independent interest", 
      "factor approximation", 
      "problem", 
      "scheme", 
      "ranking problem", 
      "approximation", 
      "new technique", 
      "constraints", 
      "class", 
      "tournament", 
      "technique", 
      "results", 
      "interest", 
      "status"
    ], 
    "name": "Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems", 
    "pagination": "277-288", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000971598"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22935-0_24"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22935-0_24", 
      "https://app.dimensions.ai/details/publication/pub.1000971598"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_296.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22935-0_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/978-3-642-22935-0_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/978-3-642-22935-0_24'

Turtle is a human-readable linked data format.

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

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-22935-0_24'


 

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

105 TRIPLES      22 PREDICATES      46 URIs      39 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22935-0_24 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N9fd81cd9f3a3411fab87ca052ec0e711
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description We settle the approximability status of the Minimum Betweenness problem in tournaments by designing a polynomial time approximation scheme (PTAS). No constant factor approximation was previously known. We also introduce a more general class of so-called fragile ranking problems and construct PTASs for them. The results depend on a new technique of dealing with fragile ranking constraints and could be of independent interest.
7 schema:editor Nece66bc0a42f463db364fbb540d7e0d3
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N4616610c06994a429d58660f9c46fa8e
11 schema:keywords approximability status
12 approximation
13 approximation scheme
14 betweenness problem
15 class
16 constant factor approximation
17 constraints
18 factor approximation
19 general class
20 independent interest
21 interest
22 new technique
23 polynomial time approximation scheme
24 problem
25 ranking problem
26 results
27 scheme
28 status
29 technique
30 time approximation scheme
31 tournament
32 schema:name Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
33 schema:pagination 277-288
34 schema:productId N667f207e6f184ed3bb673e5f6527d7aa
35 Nf9c7b233ae4d4fb787c01c106d2f87fc
36 schema:publisher N69e62ad2ea554f46b6b21f1a1600d192
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000971598
38 https://doi.org/10.1007/978-3-642-22935-0_24
39 schema:sdDatePublished 2022-11-24T21:15
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher N10fb837e9e404bd8b8d89086e7e5402f
42 schema:url https://doi.org/10.1007/978-3-642-22935-0_24
43 sgo:license sg:explorer/license/
44 sgo:sdDataset chapters
45 rdf:type schema:Chapter
46 N10fb837e9e404bd8b8d89086e7e5402f schema:name Springer Nature - SN SciGraph project
47 rdf:type schema:Organization
48 N1b1a576089714ea0b5297714fe952a16 rdf:first sg:person.015153430167.81
49 rdf:rest rdf:nil
50 N3ccafbe73f0c4126898950c803b83436 rdf:first N5172e7c1a35c49b498b36e23cceaf2ef
51 rdf:rest Nf7df4672b4994b809121ca3177db9aa4
52 N4616610c06994a429d58660f9c46fa8e schema:isbn 978-3-642-22934-3
53 978-3-642-22935-0
54 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
55 rdf:type schema:Book
56 N49f1d3b6a0dd44bcb8ed5c47a1d986a8 schema:familyName Ravi
57 schema:givenName R.
58 rdf:type schema:Person
59 N505af87c258343fe8b0dbb2d024603f8 schema:familyName Rolim
60 schema:givenName José D. P.
61 rdf:type schema:Person
62 N5172e7c1a35c49b498b36e23cceaf2ef schema:familyName Jansen
63 schema:givenName Klaus
64 rdf:type schema:Person
65 N667f207e6f184ed3bb673e5f6527d7aa schema:name doi
66 schema:value 10.1007/978-3-642-22935-0_24
67 rdf:type schema:PropertyValue
68 N69e62ad2ea554f46b6b21f1a1600d192 schema:name Springer Nature
69 rdf:type schema:Organisation
70 N9fd81cd9f3a3411fab87ca052ec0e711 rdf:first sg:person.011636042271.02
71 rdf:rest N1b1a576089714ea0b5297714fe952a16
72 Nd28122ec251b4b66ad8200eaeada7aac rdf:first N505af87c258343fe8b0dbb2d024603f8
73 rdf:rest rdf:nil
74 Nece66bc0a42f463db364fbb540d7e0d3 rdf:first Nf1acf9d502364bdc97bacce94964396d
75 rdf:rest N3ccafbe73f0c4126898950c803b83436
76 Nf1acf9d502364bdc97bacce94964396d schema:familyName Goldberg
77 schema:givenName Leslie Ann
78 rdf:type schema:Person
79 Nf7df4672b4994b809121ca3177db9aa4 rdf:first N49f1d3b6a0dd44bcb8ed5c47a1d986a8
80 rdf:rest Nd28122ec251b4b66ad8200eaeada7aac
81 Nf9c7b233ae4d4fb787c01c106d2f87fc schema:name dimensions_id
82 schema:value pub.1000971598
83 rdf:type schema:PropertyValue
84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
85 schema:name Information and Computing Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
88 schema:name Computation Theory and Mathematics
89 rdf:type schema:DefinedTerm
90 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
91 schema:familyName Karpinski
92 schema:givenName Marek
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
94 rdf:type schema:Person
95 sg:person.015153430167.81 schema:affiliation grid-institutes:grid.481554.9
96 schema:familyName Schudy
97 schema:givenName Warren
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015153430167.81
99 rdf:type schema:Person
100 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn, Germany
101 schema:name Dept. of Computer Science, University of Bonn, Germany
102 rdf:type schema:Organization
103 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research Center, USA
104 schema:name IBM T.J. Watson Research Center, USA
105 rdf:type schema:Organization
 




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


...