Ontology type: schema:Chapter
2002-06-25
AUTHORSPiotr Berman , Marek Karpinski
ABSTRACTWe 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... »
PAGES623-632
Automata, Languages and Programming
ISBN
978-3-540-43864-9
978-3-540-45465-6
http://scigraph.springernature.com/pub.10.1007/3-540-45465-9_53
DOIhttp://dx.doi.org/10.1007/3-540-45465-9_53
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1026604548
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
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