On Some Tighter Inapproximability Results (Extended Abstract) View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1999

AUTHORS

Piotr Berman , Marek Karpinski

ABSTRACT

We give a number of improved inapproximability results, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems like MAX-2SAT and E2-LIN-2, and the bounded degree graph problems, like MIS, Node Cover, and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit approximation threshold. More... »

PAGES

200-209

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48523-6_17

DOI

http://dx.doi.org/10.1007/3-540-48523-6_17

DIMENSIONS

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


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, Pennsylvania State University, University Park, 16802, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Dept. of Computer Science, Pennsylvania State University, University Park, 16802, PA, 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": "Dept. of Computer Science, University of Bonn, 53117, Bonn, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Dept. of Computer Science, University of Bonn, 53117, Bonn, USA"
          ], 
          "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"
      }
    ], 
    "datePublished": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "We give a number of improved inapproximability results, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems like MAX-2SAT and E2-LIN-2, and the bounded degree graph problems, like MIS, Node Cover, and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit approximation threshold.", 
    "editor": [
      {
        "familyName": "Wiedermann", 
        "givenName": "Jir\u00ed", 
        "type": "Person"
      }, 
      {
        "familyName": "van Emde Boas", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Nielsen", 
        "givenName": "Mogens", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48523-6_17", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66224-2", 
        "978-3-540-48523-0"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "results", 
      "MIS", 
      "reversal", 
      "number", 
      "threshold", 
      "cut", 
      "inapproximability results", 
      "problem", 
      "satisfiability problem", 
      "MAX 2SAT", 
      "graph problems", 
      "approximation threshold", 
      "Max-Cut", 
      "inapproximability", 
      "explicit approximations", 
      "approximation", 
      "cover", 
      "improved inapproximability results"
    ], 
    "name": "On Some Tighter Inapproximability Results (Extended Abstract)", 
    "pagination": "200-209", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029242904"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48523-6_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48523-6_17", 
      "https://app.dimensions.ai/details/publication/pub.1029242904"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:18", 
    "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_280.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48523-6_17"
  }
]
 

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-48523-6_17'

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-48523-6_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48523-6_17'

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-48523-6_17'


 

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

97 TRIPLES      22 PREDICATES      43 URIs      36 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48523-6_17 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N6a5b7bae9fe44daa9e37cddddd7d337b
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 schema:description We give a number of improved inapproximability results, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems like MAX-2SAT and E2-LIN-2, and the bounded degree graph problems, like MIS, Node Cover, and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit approximation threshold.
7 schema:editor Ne9aeb9d4afd84a5d90f144747e5a0786
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N06c432ec975d465097642bb33b86f100
11 schema:keywords MAX 2SAT
12 MIS
13 Max-Cut
14 approximation
15 approximation threshold
16 cover
17 cut
18 explicit approximations
19 graph problems
20 improved inapproximability results
21 inapproximability
22 inapproximability results
23 number
24 problem
25 results
26 reversal
27 satisfiability problem
28 threshold
29 schema:name On Some Tighter Inapproximability Results (Extended Abstract)
30 schema:pagination 200-209
31 schema:productId N4a30c82aa2564ce8825d9944e9924c58
32 N5f2c7895b3bb43a2b892cb0ad703bc54
33 schema:publisher N53a7e99bfb3d41a18dd89b051092b194
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029242904
35 https://doi.org/10.1007/3-540-48523-6_17
36 schema:sdDatePublished 2022-08-04T17:18
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher N3c4f421e4443403b99946e7afe9a0a92
39 schema:url https://doi.org/10.1007/3-540-48523-6_17
40 sgo:license sg:explorer/license/
41 sgo:sdDataset chapters
42 rdf:type schema:Chapter
43 N06c432ec975d465097642bb33b86f100 schema:isbn 978-3-540-48523-0
44 978-3-540-66224-2
45 schema:name Automata, Languages and Programming
46 rdf:type schema:Book
47 N2b7afdf47fd64b6c81b2c6500e7a4eb8 schema:familyName van Emde Boas
48 schema:givenName Peter
49 rdf:type schema:Person
50 N3c4f421e4443403b99946e7afe9a0a92 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N4a30c82aa2564ce8825d9944e9924c58 schema:name dimensions_id
53 schema:value pub.1029242904
54 rdf:type schema:PropertyValue
55 N4b5ea46cd47a43638c59ff3dfc5f54f4 rdf:first sg:person.011636042271.02
56 rdf:rest rdf:nil
57 N4e602be108fa409b92d1ef5d9781f677 schema:familyName Wiedermann
58 schema:givenName Jirí
59 rdf:type schema:Person
60 N53a7e99bfb3d41a18dd89b051092b194 schema:name Springer Nature
61 rdf:type schema:Organisation
62 N5f2c7895b3bb43a2b892cb0ad703bc54 schema:name doi
63 schema:value 10.1007/3-540-48523-6_17
64 rdf:type schema:PropertyValue
65 N6a5b7bae9fe44daa9e37cddddd7d337b rdf:first sg:person.01274506210.27
66 rdf:rest N4b5ea46cd47a43638c59ff3dfc5f54f4
67 Ne16fb432897d46e78eaadf40aafffb39 rdf:first Nf5e91278023b473fbb6c43cea1aafb6e
68 rdf:rest rdf:nil
69 Ne9aeb9d4afd84a5d90f144747e5a0786 rdf:first N4e602be108fa409b92d1ef5d9781f677
70 rdf:rest Nedb74ab7272241ef9a89963b9ffc4c4e
71 Nedb74ab7272241ef9a89963b9ffc4c4e rdf:first N2b7afdf47fd64b6c81b2c6500e7a4eb8
72 rdf:rest Ne16fb432897d46e78eaadf40aafffb39
73 Nf5e91278023b473fbb6c43cea1aafb6e schema:familyName Nielsen
74 schema:givenName Mogens
75 rdf:type schema:Person
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
80 schema:name Computation Theory and Mathematics
81 rdf:type schema:DefinedTerm
82 sg:person.011636042271.02 schema:affiliation grid-institutes:None
83 schema:familyName Karpinski
84 schema:givenName Marek
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
86 rdf:type schema:Person
87 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
88 schema:familyName Berman
89 schema:givenName Piotr
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
91 rdf:type schema:Person
92 grid-institutes:None schema:alternateName Dept. of Computer Science, University of Bonn, 53117, Bonn, USA
93 schema:name Dept. of Computer Science, University of Bonn, 53117, Bonn, USA
94 rdf:type schema:Organization
95 grid-institutes:grid.29857.31 schema:alternateName Dept. of Computer Science, Pennsylvania State University, University Park, 16802, PA, USA
96 schema:name Dept. of Computer Science, Pennsylvania State University, University Park, 16802, PA, USA
97 rdf:type schema:Organization
 




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


...