Ontology type: schema:Chapter Open Access: True
2015-06-20
AUTHORSAmey Bhangale , Swastik Kopparty , Sushant Sachdeva
ABSTRACTGiven k collections of 2SAT clauses on the same set of variables V, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.Our main result is that for every CSP F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document}, for , there is a polynomial time constant factor Pareto approximation algorithm for k simultaneous Max-F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document}-CSP instances. Our methods are quite general, and we also use them to give an improved approximation factor for simultaneous Max-w-SAT (for ). In contrast, for k=ω(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = \omega (\log n)$$\end{document}, no nonzero approximation factor for k simultaneous Max-F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document}-CSP instances can be achieved in polynomial time (assuming the Exponential Time Hypothesis).These problems are a natural meeting point for the theory of constraint satisfaction problems and multiobjective optimization. We also suggest a number of interesting directions for future research. More... »
PAGES193-205
Automata, Languages, and Programming
ISBN
978-3-662-47671-0
978-3-662-47672-7
http://scigraph.springernature.com/pub.10.1007/978-3-662-47672-7_16
DOIhttp://dx.doi.org/10.1007/978-3-662-47672-7_16
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1049324180
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": "Department of Computer Science, Rutgers University, New Brunswick, USA",
"id": "http://www.grid.ac/institutes/grid.430387.b",
"name": [
"Department of Computer Science, Rutgers University, New Brunswick, USA"
],
"type": "Organization"
},
"familyName": "Bhangale",
"givenName": "Amey",
"id": "sg:person.010014126735.21",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010014126735.21"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics and Department of Computer Science, Rutgers University, New Brunswick, USA",
"id": "http://www.grid.ac/institutes/grid.430387.b",
"name": [
"Department of Mathematics and Department of Computer Science, Rutgers University, New Brunswick, USA"
],
"type": "Organization"
},
"familyName": "Kopparty",
"givenName": "Swastik",
"id": "sg:person.014276170447.16",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, Yale University, New Haven, USA",
"id": "http://www.grid.ac/institutes/grid.47100.32",
"name": [
"Department of Computer Science, Yale University, New Haven, USA"
],
"type": "Organization"
},
"familyName": "Sachdeva",
"givenName": "Sushant",
"id": "sg:person.0625415211.77",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0625415211.77"
],
"type": "Person"
}
],
"datePublished": "2015-06-20",
"datePublishedReg": "2015-06-20",
"description": "Given k collections of 2SAT clauses on the same set of variables V, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.Our main result is that for every CSP F\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\mathcal {F}}$$\\end{document}, for , there is a polynomial time constant factor Pareto approximation algorithm for k simultaneous Max-F\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\mathcal {F}}$$\\end{document}-CSP instances. Our methods are quite general, and we also use them to give an improved approximation factor for simultaneous Max-w-SAT (for ). In contrast, for k=\u03c9(logn)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k = \\omega (\\log n)$$\\end{document}, no nonzero approximation factor for k simultaneous Max-F\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\mathcal {F}}$$\\end{document}-CSP instances can be achieved in polynomial time (assuming the Exponential Time Hypothesis).These problems are a natural meeting point for the theory of constraint satisfaction problems and multiobjective optimization. We also suggest a number of interesting directions for future research.",
"editor": [
{
"familyName": "Halld\u00f3rsson",
"givenName": "Magn\u00fas M.",
"type": "Person"
},
{
"familyName": "Iwama",
"givenName": "Kazuo",
"type": "Person"
},
{
"familyName": "Kobayashi",
"givenName": "Naoki",
"type": "Person"
},
{
"familyName": "Speckmann",
"givenName": "Bettina",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-662-47672-7_16",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-662-47671-0",
"978-3-662-47672-7"
],
"name": "Automata, Languages, and Programming",
"type": "Book"
},
"keywords": [
"constraint satisfaction problems",
"satisfaction problems",
"approximation algorithm",
"CSP instances",
"approximation factor",
"first nontrivial approximation algorithm",
"improved approximation factors",
"polynomial time",
"nontrivial approximation algorithm",
"multiobjective optimization",
"interesting directions",
"algorithm",
"same set",
"variable v",
"instances",
"collection",
"CSP",
"SAT",
"meeting point",
"set",
"optimization",
"clauses",
"assignment",
"context",
"method",
"max",
"future research",
"research",
"number",
"simultaneous approximation",
"time",
"point",
"main results",
"results",
"direction",
"approximation",
"large fraction",
"theory",
"factors",
"contrast",
"fraction",
"problem",
"natural meeting point"
],
"name": "Simultaneous Approximation of Constraint Satisfaction Problems",
"pagination": "193-205",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1049324180"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-662-47672-7_16"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-662-47672-7_16",
"https://app.dimensions.ai/details/publication/pub.1049324180"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-06-01T22:29",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_217.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-662-47672-7_16"
}
]
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/978-3-662-47672-7_16'
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/978-3-662-47672-7_16'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-47672-7_16'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-47672-7_16'
This table displays all metadata directly associated to this object as RDF triples.
137 TRIPLES
23 PREDICATES
68 URIs
61 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/978-3-662-47672-7_16 | schema:about | anzsrc-for:01 |
2 | ″ | ″ | anzsrc-for:0103 |
3 | ″ | schema:author | N503907e59547495884391ffb16427c0e |
4 | ″ | schema:datePublished | 2015-06-20 |
5 | ″ | schema:datePublishedReg | 2015-06-20 |
6 | ″ | schema:description | Given k collections of 2SAT clauses on the same set of variables V, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.Our main result is that for every CSP F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document}, for , there is a polynomial time constant factor Pareto approximation algorithm for k simultaneous Max-F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document}-CSP instances. Our methods are quite general, and we also use them to give an improved approximation factor for simultaneous Max-w-SAT (for ). In contrast, for k=ω(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = \omega (\log n)$$\end{document}, no nonzero approximation factor for k simultaneous Max-F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document}-CSP instances can be achieved in polynomial time (assuming the Exponential Time Hypothesis).These problems are a natural meeting point for the theory of constraint satisfaction problems and multiobjective optimization. We also suggest a number of interesting directions for future research. |
7 | ″ | schema:editor | N5dd172219f7a40deae3cc56283864b02 |
8 | ″ | schema:genre | chapter |
9 | ″ | schema:inLanguage | en |
10 | ″ | schema:isAccessibleForFree | true |
11 | ″ | schema:isPartOf | Nc21334e39f6e4e7cb439841a2e4e5437 |
12 | ″ | schema:keywords | CSP |
13 | ″ | ″ | CSP instances |
14 | ″ | ″ | SAT |
15 | ″ | ″ | algorithm |
16 | ″ | ″ | approximation |
17 | ″ | ″ | approximation algorithm |
18 | ″ | ″ | approximation factor |
19 | ″ | ″ | assignment |
20 | ″ | ″ | clauses |
21 | ″ | ″ | collection |
22 | ″ | ″ | constraint satisfaction problems |
23 | ″ | ″ | context |
24 | ″ | ″ | contrast |
25 | ″ | ″ | direction |
26 | ″ | ″ | factors |
27 | ″ | ″ | first nontrivial approximation algorithm |
28 | ″ | ″ | fraction |
29 | ″ | ″ | future research |
30 | ″ | ″ | improved approximation factors |
31 | ″ | ″ | instances |
32 | ″ | ″ | interesting directions |
33 | ″ | ″ | large fraction |
34 | ″ | ″ | main results |
35 | ″ | ″ | max |
36 | ″ | ″ | meeting point |
37 | ″ | ″ | method |
38 | ″ | ″ | multiobjective optimization |
39 | ″ | ″ | natural meeting point |
40 | ″ | ″ | nontrivial approximation algorithm |
41 | ″ | ″ | number |
42 | ″ | ″ | optimization |
43 | ″ | ″ | point |
44 | ″ | ″ | polynomial time |
45 | ″ | ″ | problem |
46 | ″ | ″ | research |
47 | ″ | ″ | results |
48 | ″ | ″ | same set |
49 | ″ | ″ | satisfaction problems |
50 | ″ | ″ | set |
51 | ″ | ″ | simultaneous approximation |
52 | ″ | ″ | theory |
53 | ″ | ″ | time |
54 | ″ | ″ | variable v |
55 | ″ | schema:name | Simultaneous Approximation of Constraint Satisfaction Problems |
56 | ″ | schema:pagination | 193-205 |
57 | ″ | schema:productId | N420a59d97dd44a73b446429d525814af |
58 | ″ | ″ | N832e641366b14f39b23642836a9c8f1f |
59 | ″ | schema:publisher | N7196f95662de4e649fdd33baa9d5e401 |
60 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1049324180 |
61 | ″ | ″ | https://doi.org/10.1007/978-3-662-47672-7_16 |
62 | ″ | schema:sdDatePublished | 2022-06-01T22:29 |
63 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
64 | ″ | schema:sdPublisher | Nc7ecf0312e894fe582d4f9241c831bf6 |
65 | ″ | schema:url | https://doi.org/10.1007/978-3-662-47672-7_16 |
66 | ″ | sgo:license | sg:explorer/license/ |
67 | ″ | sgo:sdDataset | chapters |
68 | ″ | rdf:type | schema:Chapter |
69 | N1e510a0a0b9e4982898c57e1c703ba3f | rdf:first | sg:person.0625415211.77 |
70 | ″ | rdf:rest | rdf:nil |
71 | N420a59d97dd44a73b446429d525814af | schema:name | doi |
72 | ″ | schema:value | 10.1007/978-3-662-47672-7_16 |
73 | ″ | rdf:type | schema:PropertyValue |
74 | N503907e59547495884391ffb16427c0e | rdf:first | sg:person.010014126735.21 |
75 | ″ | rdf:rest | Naa3f71dbbafe4148ab64f3d086895cf8 |
76 | N5ceaa1e4b9ac49c78953ec3074fb0429 | schema:familyName | Halldórsson |
77 | ″ | schema:givenName | Magnús M. |
78 | ″ | rdf:type | schema:Person |
79 | N5dd172219f7a40deae3cc56283864b02 | rdf:first | N5ceaa1e4b9ac49c78953ec3074fb0429 |
80 | ″ | rdf:rest | Na4efbe5a17d6408da4905deaabaffada |
81 | N7196f95662de4e649fdd33baa9d5e401 | schema:name | Springer Nature |
82 | ″ | rdf:type | schema:Organisation |
83 | N772b6f76a49e42a1bc7eb4745acf0448 | schema:familyName | Kobayashi |
84 | ″ | schema:givenName | Naoki |
85 | ″ | rdf:type | schema:Person |
86 | N7e7034e9cd38467c83dc33a7f7895eb7 | rdf:first | Nb585511f3cc1484b93242ea56489ce09 |
87 | ″ | rdf:rest | rdf:nil |
88 | N832e641366b14f39b23642836a9c8f1f | schema:name | dimensions_id |
89 | ″ | schema:value | pub.1049324180 |
90 | ″ | rdf:type | schema:PropertyValue |
91 | Na4efbe5a17d6408da4905deaabaffada | rdf:first | Ne21fa8beea2e4d42a24601df673867b9 |
92 | ″ | rdf:rest | Nbfb778006647450aaf51dae1c526c03f |
93 | Naa3f71dbbafe4148ab64f3d086895cf8 | rdf:first | sg:person.014276170447.16 |
94 | ″ | rdf:rest | N1e510a0a0b9e4982898c57e1c703ba3f |
95 | Nb585511f3cc1484b93242ea56489ce09 | schema:familyName | Speckmann |
96 | ″ | schema:givenName | Bettina |
97 | ″ | rdf:type | schema:Person |
98 | Nbfb778006647450aaf51dae1c526c03f | rdf:first | N772b6f76a49e42a1bc7eb4745acf0448 |
99 | ″ | rdf:rest | N7e7034e9cd38467c83dc33a7f7895eb7 |
100 | Nc21334e39f6e4e7cb439841a2e4e5437 | schema:isbn | 978-3-662-47671-0 |
101 | ″ | ″ | 978-3-662-47672-7 |
102 | ″ | schema:name | Automata, Languages, and Programming |
103 | ″ | rdf:type | schema:Book |
104 | Nc7ecf0312e894fe582d4f9241c831bf6 | schema:name | Springer Nature - SN SciGraph project |
105 | ″ | rdf:type | schema:Organization |
106 | Ne21fa8beea2e4d42a24601df673867b9 | schema:familyName | Iwama |
107 | ″ | schema:givenName | Kazuo |
108 | ″ | rdf:type | schema:Person |
109 | anzsrc-for:01 | schema:inDefinedTermSet | anzsrc-for: |
110 | ″ | schema:name | Mathematical Sciences |
111 | ″ | rdf:type | schema:DefinedTerm |
112 | anzsrc-for:0103 | schema:inDefinedTermSet | anzsrc-for: |
113 | ″ | schema:name | Numerical and Computational Mathematics |
114 | ″ | rdf:type | schema:DefinedTerm |
115 | sg:person.010014126735.21 | schema:affiliation | grid-institutes:grid.430387.b |
116 | ″ | schema:familyName | Bhangale |
117 | ″ | schema:givenName | Amey |
118 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010014126735.21 |
119 | ″ | rdf:type | schema:Person |
120 | sg:person.014276170447.16 | schema:affiliation | grid-institutes:grid.430387.b |
121 | ″ | schema:familyName | Kopparty |
122 | ″ | schema:givenName | Swastik |
123 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16 |
124 | ″ | rdf:type | schema:Person |
125 | sg:person.0625415211.77 | schema:affiliation | grid-institutes:grid.47100.32 |
126 | ″ | schema:familyName | Sachdeva |
127 | ″ | schema:givenName | Sushant |
128 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0625415211.77 |
129 | ″ | rdf:type | schema:Person |
130 | grid-institutes:grid.430387.b | schema:alternateName | Department of Computer Science, Rutgers University, New Brunswick, USA |
131 | ″ | ″ | Department of Mathematics and Department of Computer Science, Rutgers University, New Brunswick, USA |
132 | ″ | schema:name | Department of Computer Science, Rutgers University, New Brunswick, USA |
133 | ″ | ″ | Department of Mathematics and Department of Computer Science, Rutgers University, New Brunswick, USA |
134 | ″ | rdf:type | schema:Organization |
135 | grid-institutes:grid.47100.32 | schema:alternateName | Department of Computer Science, Yale University, New Haven, USA |
136 | ″ | schema:name | Department of Computer Science, Yale University, New Haven, USA |
137 | ″ | rdf:type | schema:Organization |