Simultaneous Approximation of Constraint Satisfaction Problems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015-06-20

AUTHORS

Amey Bhangale , Swastik Kopparty , Sushant Sachdeva

ABSTRACT

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. More... »

PAGES

193-205

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-47672-7_16

DOI

http://dx.doi.org/10.1007/978-3-662-47672-7_16

DIMENSIONS

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


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": "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", 
    "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 factor", 
      "polynomial time", 
      "nontrivial approximation algorithm", 
      "multiobjective optimization", 
      "interesting directions", 
      "algorithm", 
      "same set", 
      "instances", 
      "collection", 
      "variable v", 
      "CSP", 
      "meeting point", 
      "set", 
      "optimization", 
      "clauses", 
      "assignment", 
      "context", 
      "method", 
      "future research", 
      "research", 
      "simultaneous approximation", 
      "max", 
      "number", 
      "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-08-04T17:16", 
    "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_21.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

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/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.

135 TRIPLES      22 PREDICATES      66 URIs      59 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 N95d2c64d5dec4e24ba908afb8414014d
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 Nc3fc9c61879d470abe3284d7b53e343f
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N3e3de61a2e4c4505acc28a17c4b9e3b4
11 schema:keywords CSP
12 CSP instances
13 algorithm
14 approximation
15 approximation algorithm
16 approximation factor
17 assignment
18 clauses
19 collection
20 constraint satisfaction problems
21 context
22 contrast
23 direction
24 factors
25 first nontrivial approximation algorithm
26 fraction
27 future research
28 improved approximation factor
29 instances
30 interesting directions
31 large fraction
32 main results
33 max
34 meeting point
35 method
36 multiobjective optimization
37 natural meeting point
38 nontrivial approximation algorithm
39 number
40 optimization
41 point
42 polynomial time
43 problem
44 research
45 results
46 same set
47 satisfaction problems
48 set
49 simultaneous approximation
50 theory
51 time
52 variable v
53 schema:name Simultaneous Approximation of Constraint Satisfaction Problems
54 schema:pagination 193-205
55 schema:productId N4239a27ebe1e4204ad4912cf13050d2f
56 Nda865af65e574025b5132b712443e1f5
57 schema:publisher Nd66e3e70a7694916956019c87d961e6b
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049324180
59 https://doi.org/10.1007/978-3-662-47672-7_16
60 schema:sdDatePublished 2022-08-04T17:16
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher Nd42c415a0c2b4346a60ef1d8c15c598a
63 schema:url https://doi.org/10.1007/978-3-662-47672-7_16
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N0f0ea7217eda47199cb24f44514eea2b schema:familyName Kobayashi
68 schema:givenName Naoki
69 rdf:type schema:Person
70 N285b2c8707e9474d9785a8c85682988c schema:familyName Iwama
71 schema:givenName Kazuo
72 rdf:type schema:Person
73 N2913a7326e614a50abdc19a9db411122 schema:familyName Halldórsson
74 schema:givenName Magnús M.
75 rdf:type schema:Person
76 N2d0d6e3c10fe4520b98fa8cee3f4ea9a schema:familyName Speckmann
77 schema:givenName Bettina
78 rdf:type schema:Person
79 N3e3de61a2e4c4505acc28a17c4b9e3b4 schema:isbn 978-3-662-47671-0
80 978-3-662-47672-7
81 schema:name Automata, Languages, and Programming
82 rdf:type schema:Book
83 N4239a27ebe1e4204ad4912cf13050d2f schema:name dimensions_id
84 schema:value pub.1049324180
85 rdf:type schema:PropertyValue
86 N534aa0f8fff843a0bfba0f1422098f03 rdf:first sg:person.0625415211.77
87 rdf:rest rdf:nil
88 N5d9f3e5061614b60b4d22f985163289b rdf:first sg:person.014276170447.16
89 rdf:rest N534aa0f8fff843a0bfba0f1422098f03
90 N95d2c64d5dec4e24ba908afb8414014d rdf:first sg:person.010014126735.21
91 rdf:rest N5d9f3e5061614b60b4d22f985163289b
92 N987cfb9c6aaf41d09ac3645c81e59638 rdf:first N0f0ea7217eda47199cb24f44514eea2b
93 rdf:rest Nca87610288f34c6e97cc5590accb071f
94 Nc3fc9c61879d470abe3284d7b53e343f rdf:first N2913a7326e614a50abdc19a9db411122
95 rdf:rest Nfdc4fc96e1bd424085edc3d66eba7394
96 Nca87610288f34c6e97cc5590accb071f rdf:first N2d0d6e3c10fe4520b98fa8cee3f4ea9a
97 rdf:rest rdf:nil
98 Nd42c415a0c2b4346a60ef1d8c15c598a schema:name Springer Nature - SN SciGraph project
99 rdf:type schema:Organization
100 Nd66e3e70a7694916956019c87d961e6b schema:name Springer Nature
101 rdf:type schema:Organisation
102 Nda865af65e574025b5132b712443e1f5 schema:name doi
103 schema:value 10.1007/978-3-662-47672-7_16
104 rdf:type schema:PropertyValue
105 Nfdc4fc96e1bd424085edc3d66eba7394 rdf:first N285b2c8707e9474d9785a8c85682988c
106 rdf:rest N987cfb9c6aaf41d09ac3645c81e59638
107 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
108 schema:name Mathematical Sciences
109 rdf:type schema:DefinedTerm
110 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
111 schema:name Numerical and Computational Mathematics
112 rdf:type schema:DefinedTerm
113 sg:person.010014126735.21 schema:affiliation grid-institutes:grid.430387.b
114 schema:familyName Bhangale
115 schema:givenName Amey
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010014126735.21
117 rdf:type schema:Person
118 sg:person.014276170447.16 schema:affiliation grid-institutes:grid.430387.b
119 schema:familyName Kopparty
120 schema:givenName Swastik
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16
122 rdf:type schema:Person
123 sg:person.0625415211.77 schema:affiliation grid-institutes:grid.47100.32
124 schema:familyName Sachdeva
125 schema:givenName Sushant
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0625415211.77
127 rdf:type schema:Person
128 grid-institutes:grid.430387.b schema:alternateName Department of Computer Science, Rutgers University, New Brunswick, USA
129 Department of Mathematics and Department of Computer Science, Rutgers University, New Brunswick, USA
130 schema:name Department of Computer Science, Rutgers University, New Brunswick, USA
131 Department of Mathematics and Department of Computer Science, Rutgers University, New Brunswick, USA
132 rdf:type schema:Organization
133 grid-institutes:grid.47100.32 schema:alternateName Department of Computer Science, Yale University, New Haven, USA
134 schema:name Department of Computer Science, Yale University, New Haven, USA
135 rdf:type schema:Organization
 




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


...