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-10-01T06:53", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_200.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 N3f0afade16a04b50be59c4e9954f0f66
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 N5ece3113159147999d1a04385801411b
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nf26134c2e7a949fd8903be74a316e7bb
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 N0c96d922ebc14d4cb9eeb3c78b5f8b13
32 N1b93124df498464c8221b8200fca1c33
33 schema:publisher N2190b8b7b13449479856d09ad8a92d1f
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-10-01T06:53
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher N6a3a4f14707d4fc6a1e7c744cf674299
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 N0c96d922ebc14d4cb9eeb3c78b5f8b13 schema:name dimensions_id
44 schema:value pub.1029242904
45 rdf:type schema:PropertyValue
46 N1b93124df498464c8221b8200fca1c33 schema:name doi
47 schema:value 10.1007/3-540-48523-6_17
48 rdf:type schema:PropertyValue
49 N2190b8b7b13449479856d09ad8a92d1f schema:name Springer Nature
50 rdf:type schema:Organisation
51 N3c083cdd2c8f441e85cb698dc50b4f41 rdf:first sg:person.011636042271.02
52 rdf:rest rdf:nil
53 N3cb2152044ec46a0aa0c4b1c3a77c938 rdf:first N45746846f1d243afab4a55450d34c36f
54 rdf:rest Nc3e0e68f169645009c5a0f96164fd31d
55 N3f0afade16a04b50be59c4e9954f0f66 rdf:first sg:person.01274506210.27
56 rdf:rest N3c083cdd2c8f441e85cb698dc50b4f41
57 N45746846f1d243afab4a55450d34c36f schema:familyName van Emde Boas
58 schema:givenName Peter
59 rdf:type schema:Person
60 N4da55f2dac284c3d90e36fedc2694630 schema:familyName Wiedermann
61 schema:givenName Jirí
62 rdf:type schema:Person
63 N5ece3113159147999d1a04385801411b rdf:first N4da55f2dac284c3d90e36fedc2694630
64 rdf:rest N3cb2152044ec46a0aa0c4b1c3a77c938
65 N6a3a4f14707d4fc6a1e7c744cf674299 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 Nb6ab1ea0d4a849098af9c968fa3766f7 schema:familyName Nielsen
68 schema:givenName Mogens
69 rdf:type schema:Person
70 Nc3e0e68f169645009c5a0f96164fd31d rdf:first Nb6ab1ea0d4a849098af9c968fa3766f7
71 rdf:rest rdf:nil
72 Nf26134c2e7a949fd8903be74a316e7bb schema:isbn 978-3-540-48523-0
73 978-3-540-66224-2
74 schema:name Automata, Languages and Programming
75 rdf:type schema:Book
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)


...