Approximating Bounded Degree Instances of NP-Hard Problems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-08-02

AUTHORS

Marek Karpinski

ABSTRACT

We present some of the recent results on computational complexity of approximating bounded degree combinatorial optimization problems. In particular, we present the best up to now known explicit nonapproximability bounds on the very small degree optimization problems which are of particular importance on the intermediate stages of proving approximation hardness of some other generic optimization problems. More... »

PAGES

24-34

Book

TITLE

Fundamentals of Computation Theory

ISBN

978-3-540-42487-1
978-3-540-44669-9

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44669-9_4

DOI

http://dx.doi.org/10.1007/3-540-44669-9_4

DIMENSIONS

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


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/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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "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": "University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "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"
      }
    ], 
    "datePublished": "2001-08-02", 
    "datePublishedReg": "2001-08-02", 
    "description": "We present some of the recent results on computational complexity of approximating bounded degree combinatorial optimization problems. In particular, we present the best up to now known explicit nonapproximability bounds on the very small degree optimization problems which are of particular importance on the intermediate stages of proving approximation hardness of some other generic optimization problems.", 
    "editor": [
      {
        "familyName": "Freivalds", 
        "givenName": "R\u016bsi\u0146\u0161", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44669-9_4", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42487-1", 
        "978-3-540-44669-9"
      ], 
      "name": "Fundamentals of Computation Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "optimization problem", 
      "combinatorial optimization problems", 
      "generic optimization problem", 
      "NP-hard problem", 
      "computational complexity", 
      "approximation hardness", 
      "recent results", 
      "problem", 
      "bounds", 
      "particular importance", 
      "complexity", 
      "instances", 
      "intermediate stage", 
      "results", 
      "importance", 
      "stage", 
      "hardness"
    ], 
    "name": "Approximating Bounded Degree Instances of NP-Hard Problems", 
    "pagination": "24-34", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021248395"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44669-9_4"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44669-9_4", 
      "https://app.dimensions.ai/details/publication/pub.1021248395"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:51", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_31.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44669-9_4"
  }
]
 

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-44669-9_4'

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-44669-9_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44669-9_4'

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-44669-9_4'


 

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

84 TRIPLES      22 PREDICATES      43 URIs      34 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44669-9_4 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 anzsrc-for:08
4 anzsrc-for:0802
5 schema:author N2bdb32c3b986429a8bbdefcbc37e6382
6 schema:datePublished 2001-08-02
7 schema:datePublishedReg 2001-08-02
8 schema:description We present some of the recent results on computational complexity of approximating bounded degree combinatorial optimization problems. In particular, we present the best up to now known explicit nonapproximability bounds on the very small degree optimization problems which are of particular importance on the intermediate stages of proving approximation hardness of some other generic optimization problems.
9 schema:editor N3219ce42324f435d94452daf2c7c1388
10 schema:genre chapter
11 schema:isAccessibleForFree false
12 schema:isPartOf N47c123629faa4dd695849c4b3f9dbb53
13 schema:keywords NP-hard problem
14 approximation hardness
15 bounds
16 combinatorial optimization problems
17 complexity
18 computational complexity
19 generic optimization problem
20 hardness
21 importance
22 instances
23 intermediate stage
24 optimization problem
25 particular importance
26 problem
27 recent results
28 results
29 stage
30 schema:name Approximating Bounded Degree Instances of NP-Hard Problems
31 schema:pagination 24-34
32 schema:productId Nea9dd3e10ffa4145b0a049df14d48a28
33 Nee1fa6d34f5a4dfe89528202bb56e89c
34 schema:publisher N406e18f45e3c4ec0a7284037a7c267c3
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021248395
36 https://doi.org/10.1007/3-540-44669-9_4
37 schema:sdDatePublished 2022-12-01T06:51
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N258b499f97f14112ae21716b1f17fa9b
40 schema:url https://doi.org/10.1007/3-540-44669-9_4
41 sgo:license sg:explorer/license/
42 sgo:sdDataset chapters
43 rdf:type schema:Chapter
44 N258b499f97f14112ae21716b1f17fa9b schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 N2bdb32c3b986429a8bbdefcbc37e6382 rdf:first sg:person.011636042271.02
47 rdf:rest rdf:nil
48 N3219ce42324f435d94452daf2c7c1388 rdf:first N696b25c46cb54678a8a5f1c28f845858
49 rdf:rest rdf:nil
50 N406e18f45e3c4ec0a7284037a7c267c3 schema:name Springer Nature
51 rdf:type schema:Organisation
52 N47c123629faa4dd695849c4b3f9dbb53 schema:isbn 978-3-540-42487-1
53 978-3-540-44669-9
54 schema:name Fundamentals of Computation Theory
55 rdf:type schema:Book
56 N696b25c46cb54678a8a5f1c28f845858 schema:familyName Freivalds
57 schema:givenName Rūsiņš
58 rdf:type schema:Person
59 Nea9dd3e10ffa4145b0a049df14d48a28 schema:name doi
60 schema:value 10.1007/3-540-44669-9_4
61 rdf:type schema:PropertyValue
62 Nee1fa6d34f5a4dfe89528202bb56e89c schema:name dimensions_id
63 schema:value pub.1021248395
64 rdf:type schema:PropertyValue
65 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
66 schema:name Mathematical Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
69 schema:name Numerical and Computational Mathematics
70 rdf:type schema:DefinedTerm
71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
72 schema:name Information and Computing Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
75 schema:name Computation Theory and Mathematics
76 rdf:type schema:DefinedTerm
77 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
78 schema:familyName Karpinski
79 schema:givenName Marek
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
81 rdf:type schema:Person
82 grid-institutes:grid.10388.32 schema:alternateName University of Bonn, Germany
83 schema:name University of Bonn, Germany
84 rdf:type schema:Organization
 




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


...