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", 
    "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

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.

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
 




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


...