Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1998

AUTHORS

Philip N. Klein , Hsueh-I Lu

ABSTRACT

The essential part of the best known approximation algorithm for graph MAXCUT is approximately solving MAXCUT’s semidefinite relaxation. For a graph with n nodes and m edges, previous work on solving its semidefinite relaxation for MAXCUT requires space Õ(n2). Under the assumption of exact arithmetic, we show how an approximate solution can be found in space O(m + n1.5), where O(m) comes from the input; and therefore reduce the space required by the best known approximation algorithm for graph MAXCUT.Using the above space-efficient algorithm as a subroutine, we show an approximate solution for COLORING’s semidefinite relaxation can be found in space O(m)+ Õ(n1.5). This reduces not only the space required by the best known approximation algorithm for graph COLORING, but also the space required by the only known polynomial-time algorithm for finding a maximum clique in a perfect graph. More... »

PAGES

388-398

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-49381-6_41

DOI

http://dx.doi.org/10.1007/3-540-49381-6_41

DIMENSIONS

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


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": "Department of Computer Science, Brown University, USA", 
          "id": "http://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Klein", 
        "givenName": "Philip N.", 
        "id": "sg:person.0701364100.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0701364100.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Chung-Cheng University, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung-Cheng University, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "The essential part of the best known approximation algorithm for graph MAXCUT is approximately solving MAXCUT\u2019s semidefinite relaxation. For a graph with n nodes and m edges, previous work on solving its semidefinite relaxation for MAXCUT requires space \u00d5(n2). Under the assumption of exact arithmetic, we show how an approximate solution can be found in space O(m + n1.5), where O(m) comes from the input; and therefore reduce the space required by the best known approximation algorithm for graph MAXCUT.Using the above space-efficient algorithm as a subroutine, we show an approximate solution for COLORING\u2019s semidefinite relaxation can be found in space O(m)+ \u00d5(n1.5). This reduces not only the space required by the best known approximation algorithm for graph COLORING, but also the space required by the only known polynomial-time algorithm for finding a maximum clique in a perfect graph.", 
    "editor": [
      {
        "familyName": "Chwa", 
        "givenName": "Kyung-Yong", 
        "type": "Person"
      }, 
      {
        "familyName": "Ibarra", 
        "givenName": "Oscar H.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-49381-6_41", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-65385-1", 
        "978-3-540-49381-5"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "semidefinite relaxation", 
      "approximation algorithm", 
      "approximate solution", 
      "semidefinite program", 
      "maximum clique", 
      "space-efficient algorithms", 
      "polynomial time algorithm", 
      "graph coloring", 
      "MaxCut", 
      "perfect graphs", 
      "algorithm", 
      "space", 
      "graph", 
      "solution", 
      "relaxation", 
      "previous work", 
      "cliques", 
      "coloring", 
      "assumption", 
      "subroutine", 
      "input", 
      "nodes", 
      "essential part", 
      "work", 
      "part", 
      "program"
    ], 
    "name": "Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs", 
    "pagination": "388-398", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035998677"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-49381-6_41"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-49381-6_41", 
      "https://app.dimensions.ai/details/publication/pub.1035998677"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_31.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-49381-6_41"
  }
]
 

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-49381-6_41'

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-49381-6_41'

Turtle is a human-readable linked data format.

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

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-49381-6_41'


 

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

101 TRIPLES      23 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-49381-6_41 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Na58ede0e1434473cafb45b2c99dad1bb
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description The essential part of the best known approximation algorithm for graph MAXCUT is approximately solving MAXCUT’s semidefinite relaxation. For a graph with n nodes and m edges, previous work on solving its semidefinite relaxation for MAXCUT requires space Õ(n2). Under the assumption of exact arithmetic, we show how an approximate solution can be found in space O(m + n1.5), where O(m) comes from the input; and therefore reduce the space required by the best known approximation algorithm for graph MAXCUT.Using the above space-efficient algorithm as a subroutine, we show an approximate solution for COLORING’s semidefinite relaxation can be found in space O(m)+ Õ(n1.5). This reduces not only the space required by the best known approximation algorithm for graph COLORING, but also the space required by the only known polynomial-time algorithm for finding a maximum clique in a perfect graph.
7 schema:editor N7c9af8d9f44544bba31c0db2b80ae8f1
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N7adf7829625c4818a03c5e5970a62c63
12 schema:keywords MaxCut
13 algorithm
14 approximate solution
15 approximation algorithm
16 assumption
17 cliques
18 coloring
19 essential part
20 graph
21 graph coloring
22 input
23 maximum clique
24 nodes
25 part
26 perfect graphs
27 polynomial time algorithm
28 previous work
29 program
30 relaxation
31 semidefinite program
32 semidefinite relaxation
33 solution
34 space
35 space-efficient algorithms
36 subroutine
37 work
38 schema:name Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs
39 schema:pagination 388-398
40 schema:productId N4c7566dd9d0240b0a6cb6d7ee5bfd2e9
41 Nfd9b9aa9d3af409d82c9c5f976620201
42 schema:publisher N8aeab410e69d4662a670072d71d476ae
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035998677
44 https://doi.org/10.1007/3-540-49381-6_41
45 schema:sdDatePublished 2022-05-20T07:45
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher Nb85aa5a5db56412f9eb7e47338fe23e1
48 schema:url https://doi.org/10.1007/3-540-49381-6_41
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N2b7546c66db44d3ebab3caf998439474 schema:familyName Chwa
53 schema:givenName Kyung-Yong
54 rdf:type schema:Person
55 N4c7566dd9d0240b0a6cb6d7ee5bfd2e9 schema:name dimensions_id
56 schema:value pub.1035998677
57 rdf:type schema:PropertyValue
58 N7adf7829625c4818a03c5e5970a62c63 schema:isbn 978-3-540-49381-5
59 978-3-540-65385-1
60 schema:name Algorithms and Computation
61 rdf:type schema:Book
62 N7c9af8d9f44544bba31c0db2b80ae8f1 rdf:first N2b7546c66db44d3ebab3caf998439474
63 rdf:rest N881f280f89744770a2383dbbad4055b6
64 N881f280f89744770a2383dbbad4055b6 rdf:first N8b10db689f8f46f3ae4dfbc6c514ce9f
65 rdf:rest rdf:nil
66 N8aeab410e69d4662a670072d71d476ae schema:name Springer Nature
67 rdf:type schema:Organisation
68 N8b10db689f8f46f3ae4dfbc6c514ce9f schema:familyName Ibarra
69 schema:givenName Oscar H.
70 rdf:type schema:Person
71 N8cae6a1e7ca840bfb1179ffa13feb4fb rdf:first sg:person.013345515575.46
72 rdf:rest rdf:nil
73 Na58ede0e1434473cafb45b2c99dad1bb rdf:first sg:person.0701364100.14
74 rdf:rest N8cae6a1e7ca840bfb1179ffa13feb4fb
75 Nb85aa5a5db56412f9eb7e47338fe23e1 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 Nfd9b9aa9d3af409d82c9c5f976620201 schema:name doi
78 schema:value 10.1007/3-540-49381-6_41
79 rdf:type schema:PropertyValue
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.412047.4
87 schema:familyName Lu
88 schema:givenName Hsueh-I
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
90 rdf:type schema:Person
91 sg:person.0701364100.14 schema:affiliation grid-institutes:grid.40263.33
92 schema:familyName Klein
93 schema:givenName Philip N.
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0701364100.14
95 rdf:type schema:Person
96 grid-institutes:grid.40263.33 schema:alternateName Department of Computer Science, Brown University, USA
97 schema:name Department of Computer Science, Brown University, USA
98 rdf:type schema:Organization
99 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung-Cheng University, Taiwan
100 schema:name Department of Computer Science and Information Engineering, National Chung-Cheng University, Taiwan
101 rdf:type schema:Organization
 




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


...