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-08-04T17:21", 
    "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_59.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 N67b9d70b6e444b6fbf8a8700ac8346f0
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 N561dff9111284cda971f0cdf5bbe7ff0
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nf065d1e9d4ac4e6291e025ec06740cbb
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 N0e7570ce2cff43cb84ce6f32c3ec4494
43 N8e5fb2709c57412ea1b435b7df80e3d6
44 schema:publisher N4e687c1e3188496a995ca762b5cb4441
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-08-04T17:21
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher Nab1e6b6d35394098967284230eac7b0f
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 N03b7c42f83354741982799a9ec5500c0 rdf:first Nb06a7a84675246b892ccf1036c45328b
55 rdf:rest rdf:nil
56 N0e7570ce2cff43cb84ce6f32c3ec4494 schema:name doi
57 schema:value 10.1007/3-540-45465-9_53
58 rdf:type schema:PropertyValue
59 N10bb97bcdaab4918b167bcaf9d9d2e56 rdf:first Nfda7a98dc43a4f60862e33d451f88deb
60 rdf:rest N5377020486a343d4908410b4df4bf65e
61 N478e3c16f71a4ad98b70821516a64cf4 rdf:first sg:person.011636042271.02
62 rdf:rest rdf:nil
63 N4e687c1e3188496a995ca762b5cb4441 schema:name Springer Nature
64 rdf:type schema:Organisation
65 N5377020486a343d4908410b4df4bf65e rdf:first N85a01652aa694d8692bd91b923dd2530
66 rdf:rest N5b1c1051def44da59e442a0bda59b95e
67 N561dff9111284cda971f0cdf5bbe7ff0 rdf:first N9496b0a01ab2463ba9519b17f25f125d
68 rdf:rest N10bb97bcdaab4918b167bcaf9d9d2e56
69 N5a1716ca3446435a86075b28ca01cda6 rdf:first N860ed78604284c508c8847a619e1cc66
70 rdf:rest N03b7c42f83354741982799a9ec5500c0
71 N5b1c1051def44da59e442a0bda59b95e rdf:first Nbfcdded230994e06a8a51d9258bb648b
72 rdf:rest N5a1716ca3446435a86075b28ca01cda6
73 N67b9d70b6e444b6fbf8a8700ac8346f0 rdf:first sg:person.01274506210.27
74 rdf:rest N478e3c16f71a4ad98b70821516a64cf4
75 N85a01652aa694d8692bd91b923dd2530 schema:familyName Triguero
76 schema:givenName Francisco
77 rdf:type schema:Person
78 N860ed78604284c508c8847a619e1cc66 schema:familyName Conejo
79 schema:givenName Ricardo
80 rdf:type schema:Person
81 N8e5fb2709c57412ea1b435b7df80e3d6 schema:name dimensions_id
82 schema:value pub.1026604548
83 rdf:type schema:PropertyValue
84 N9496b0a01ab2463ba9519b17f25f125d schema:familyName Widmayer
85 schema:givenName Peter
86 rdf:type schema:Person
87 Nab1e6b6d35394098967284230eac7b0f schema:name Springer Nature - SN SciGraph project
88 rdf:type schema:Organization
89 Nb06a7a84675246b892ccf1036c45328b schema:familyName Hennessy
90 schema:givenName Matthew
91 rdf:type schema:Person
92 Nbfcdded230994e06a8a51d9258bb648b schema:familyName Morales
93 schema:givenName Rafael
94 rdf:type schema:Person
95 Nf065d1e9d4ac4e6291e025ec06740cbb schema:isbn 978-3-540-43864-9
96 978-3-540-45465-6
97 schema:name Automata, Languages and Programming
98 rdf:type schema:Book
99 Nfda7a98dc43a4f60862e33d451f88deb schema:familyName Eidenbenz
100 schema:givenName Stephan
101 rdf:type schema:Person
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)


...