Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-06-25

AUTHORS

Piotr Berman , Marek Karpinski

ABSTRACT

We consider bounded occurrence (degree) instances of a minimum constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for graphs. MIN-LIN2 is an optimization problem for a given system of linear equations mod 2 to construct a solution that satisfies the minimum number of them. E3-OCC-MIN-E3-LIN2 is the bounded occurrence (degree) problem restricted as follows: each equation has exactly 3 variables and each variable occurs in exactly 3 equations. Clearly, MIN-LIN2 is equivalent to another well known problem, the Nearest Codeword problem, and E3-OCC-MIN-E3-LIN2 to its bounded occurrence version. MIN-BISECTION is a problem of finding a minimum bisection of a graph, while 3-MIN-BISECTION is the MIN-BISECTION problem restricted to 3-regular graphs only. We show that, somewhat surprisingly, these two restricted problems are exactly as hard to approximate as their general versions. In particular, an approximation ratio lower bound for E3-OCC-MIN-E3-LIN2 (bounded 3-occurrence 3-ary Nearest Codeword problem) is equal to MIN-LIN2 (Nearest Codeword problem) lower bound nΩ(1)/log log n. Moreover, an existence of a constant factor approximation ratio (or a PTAS) for 3-MIN-BISECTION entails existence of a constant approximation ratio (or a PTAS) for the general MIN-BISECTION. More... »

PAGES

623-632

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-43864-9
978-3-540-45465-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45465-9_53

DOI

http://dx.doi.org/10.1007/3-540-45465-9_53

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, 53117, Bonn", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, 53117, Bonn"
          ], 
          "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", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, 53117, Bonn"
          ], 
          "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": "2002-06-25", 
    "datePublishedReg": "2002-06-25", 
    "description": "We consider bounded occurrence (degree) instances of a minimum constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for graphs. MIN-LIN2 is an optimization problem for a given system of linear equations mod 2 to construct a solution that satisfies the minimum number of them. E3-OCC-MIN-E3-LIN2 is the bounded occurrence (degree) problem restricted as follows: each equation has exactly 3 variables and each variable occurs in exactly 3 equations. Clearly, MIN-LIN2 is equivalent to another well known problem, the Nearest Codeword problem, and E3-OCC-MIN-E3-LIN2 to its bounded occurrence version. MIN-BISECTION is a problem of finding a minimum bisection of a graph, while 3-MIN-BISECTION is the MIN-BISECTION problem restricted to 3-regular graphs only. We show that, somewhat surprisingly, these two restricted problems are exactly as hard to approximate as their general versions. In particular, an approximation ratio lower bound for E3-OCC-MIN-E3-LIN2 (bounded 3-occurrence 3-ary Nearest Codeword problem) is equal to MIN-LIN2 (Nearest Codeword problem) lower bound n\u03a9(1)/log log n. Moreover, an existence of a constant factor approximation ratio (or a PTAS) for 3-MIN-BISECTION entails existence of a constant approximation ratio (or a PTAS) for the general MIN-BISECTION.", 
    "editor": [
      {
        "familyName": "Widmayer", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Eidenbenz", 
        "givenName": "Stephan", 
        "type": "Person"
      }, 
      {
        "familyName": "Triguero", 
        "givenName": "Francisco", 
        "type": "Person"
      }, 
      {
        "familyName": "Morales", 
        "givenName": "Rafael", 
        "type": "Person"
      }, 
      {
        "familyName": "Conejo", 
        "givenName": "Ricardo", 
        "type": "Person"
      }, 
      {
        "familyName": "Hennessy", 
        "givenName": "Matthew", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45465-9_53", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-43864-9", 
        "978-3-540-45465-6"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "min-bisection problem", 
      "Min-Bisection", 
      "approximation ratio", 
      "constant-factor approximation ratio", 
      "Nearest Codeword Problem", 
      "optimization problem", 
      "minimum bisection", 
      "constant approximation ratio", 
      "general version", 
      "Restricted Problem", 
      "approximation hardness", 
      "log n.", 
      "equations", 
      "mod 2", 
      "graph", 
      "minimum number", 
      "problem", 
      "bisection", 
      "existence", 
      "LIN2", 
      "version", 
      "solution", 
      "variables", 
      "n.", 
      "system", 
      "instances", 
      "number", 
      "ratio", 
      "hardness"
    ], 
    "name": "Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION", 
    "pagination": "623-632", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026604548"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45465-9_53"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45465-9_53", 
      "https://app.dimensions.ai/details/publication/pub.1026604548"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:59", 
    "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_431.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45465-9_53"
  }
]
 

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-45465-9_53'

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-45465-9_53'

Turtle is a human-readable linked data format.

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

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-45465-9_53'


 

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

120 TRIPLES      22 PREDICATES      53 URIs      46 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45465-9_53 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N6ae6ebda60784594849bd152a2c3c154
4 schema:datePublished 2002-06-25
5 schema:datePublishedReg 2002-06-25
6 schema:description We consider bounded occurrence (degree) instances of a minimum constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for graphs. MIN-LIN2 is an optimization problem for a given system of linear equations mod 2 to construct a solution that satisfies the minimum number of them. E3-OCC-MIN-E3-LIN2 is the bounded occurrence (degree) problem restricted as follows: each equation has exactly 3 variables and each variable occurs in exactly 3 equations. Clearly, MIN-LIN2 is equivalent to another well known problem, the Nearest Codeword problem, and E3-OCC-MIN-E3-LIN2 to its bounded occurrence version. MIN-BISECTION is a problem of finding a minimum bisection of a graph, while 3-MIN-BISECTION is the MIN-BISECTION problem restricted to 3-regular graphs only. We show that, somewhat surprisingly, these two restricted problems are exactly as hard to approximate as their general versions. In particular, an approximation ratio lower bound for E3-OCC-MIN-E3-LIN2 (bounded 3-occurrence 3-ary Nearest Codeword problem) is equal to MIN-LIN2 (Nearest Codeword problem) lower bound nΩ(1)/log log n. Moreover, an existence of a constant factor approximation ratio (or a PTAS) for 3-MIN-BISECTION entails existence of a constant approximation ratio (or a PTAS) for the general MIN-BISECTION.
7 schema:editor N5e7036db62d94004b2a08231710d36fa
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N1fda21a1ffec4f8b931da88cc74ff650
11 schema:keywords LIN2
12 Min-Bisection
13 Nearest Codeword Problem
14 Restricted Problem
15 approximation hardness
16 approximation ratio
17 bisection
18 constant approximation ratio
19 constant-factor approximation ratio
20 equations
21 existence
22 general version
23 graph
24 hardness
25 instances
26 log n.
27 min-bisection problem
28 minimum bisection
29 minimum number
30 mod 2
31 n.
32 number
33 optimization problem
34 problem
35 ratio
36 solution
37 system
38 variables
39 version
40 schema:name Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION
41 schema:pagination 623-632
42 schema:productId N3834c26516334ec491653741898550ca
43 N7e47a7e4314b4da09b54399c65297a31
44 schema:publisher Nfdc97d1fa26040f9bddca47015835cfc
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026604548
46 https://doi.org/10.1007/3-540-45465-9_53
47 schema:sdDatePublished 2022-10-01T06:59
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N4a77b10068a94798a418d8def247ee74
50 schema:url https://doi.org/10.1007/3-540-45465-9_53
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N1fda21a1ffec4f8b931da88cc74ff650 schema:isbn 978-3-540-43864-9
55 978-3-540-45465-6
56 schema:name Automata, Languages and Programming
57 rdf:type schema:Book
58 N3834c26516334ec491653741898550ca schema:name dimensions_id
59 schema:value pub.1026604548
60 rdf:type schema:PropertyValue
61 N4a77b10068a94798a418d8def247ee74 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 N4d1e832e08ca4a0b846cecb8272ec08f rdf:first sg:person.011636042271.02
64 rdf:rest rdf:nil
65 N565a36fd346d40c9a23ff00dd0974120 rdf:first Na3565b4b76494a0c85417d055b782d98
66 rdf:rest Nf144e44434c649e5b6a1a7d39e0df578
67 N5e7036db62d94004b2a08231710d36fa rdf:first Nadf3c6dbbc21478495fbc91c9d8580c9
68 rdf:rest Nf171d065fbb94bc1b029b043d8066b90
69 N6ae6ebda60784594849bd152a2c3c154 rdf:first sg:person.01274506210.27
70 rdf:rest N4d1e832e08ca4a0b846cecb8272ec08f
71 N7e47a7e4314b4da09b54399c65297a31 schema:name doi
72 schema:value 10.1007/3-540-45465-9_53
73 rdf:type schema:PropertyValue
74 Na3565b4b76494a0c85417d055b782d98 schema:familyName Morales
75 schema:givenName Rafael
76 rdf:type schema:Person
77 Nadafc8f540314286b98e86a8558534e9 rdf:first Nb5061bb8ac57404a93c59c36c4badeb9
78 rdf:rest rdf:nil
79 Nadf3c6dbbc21478495fbc91c9d8580c9 schema:familyName Widmayer
80 schema:givenName Peter
81 rdf:type schema:Person
82 Nb5061bb8ac57404a93c59c36c4badeb9 schema:familyName Hennessy
83 schema:givenName Matthew
84 rdf:type schema:Person
85 Nbb454e1995ea40fdb76e0d5b1460f64d rdf:first Nef2a77072b144667ab7ddfcf40973ac1
86 rdf:rest N565a36fd346d40c9a23ff00dd0974120
87 Nbbadd1485e0e4a718d15f6a0148fc0d0 schema:familyName Eidenbenz
88 schema:givenName Stephan
89 rdf:type schema:Person
90 Ne2cd3c6a4024480580f922c08443cc57 schema:familyName Conejo
91 schema:givenName Ricardo
92 rdf:type schema:Person
93 Nef2a77072b144667ab7ddfcf40973ac1 schema:familyName Triguero
94 schema:givenName Francisco
95 rdf:type schema:Person
96 Nf144e44434c649e5b6a1a7d39e0df578 rdf:first Ne2cd3c6a4024480580f922c08443cc57
97 rdf:rest Nadafc8f540314286b98e86a8558534e9
98 Nf171d065fbb94bc1b029b043d8066b90 rdf:first Nbbadd1485e0e4a718d15f6a0148fc0d0
99 rdf:rest Nbb454e1995ea40fdb76e0d5b1460f64d
100 Nfdc97d1fa26040f9bddca47015835cfc schema:name Springer Nature
101 rdf:type schema:Organisation
102 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
103 schema:name Mathematical Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
106 schema:name Numerical and Computational Mathematics
107 rdf:type schema:DefinedTerm
108 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
109 schema:familyName Karpinski
110 schema:givenName Marek
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
112 rdf:type schema:Person
113 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.10388.32
114 schema:familyName Berman
115 schema:givenName Piotr
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
117 rdf:type schema:Person
118 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn, 53117, Bonn
119 schema:name Dept. of Computer Science, University of Bonn, 53117, Bonn
120 rdf:type schema:Organization
 




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


...