Streaming approximation resistance of every ordering CSP
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913455430172672 |
|---|---|
| author | Singer, Noah G. Sudan, Madhu Velusamy, Santhoshini |
| author_facet | Singer, Noah G. Sudan, Madhu Velusamy, Santhoshini |
| contents | An ordering constraint satisfaction problem (OCSP) is defined by a family $\mathcal{F}$ of predicates mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. An instance of Max-OCSP($\mathcal{F}$) on $n$ variables consists of a list of constraints, each consisting of a predicate from $\mathcal{F}$ applied on $k$ distinct variables. The goal is to find an ordering of the $n$ variables that maximizes the number of constraints for which the induced ordering on the $k$ variables satisfies the predicate. OCSPs capture well-studied problems including `maximum acyclic subgraph' (MAS) and "maximum betweenness".
In this work, we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) streaming setting, when an instance is presented as a stream of constraints. We show that for every $\mathcal{F}$, Max-OCSP($\mathcal{F}$) is approximation-resistant to $o(n)$-space streaming algorithms, i.e., algorithms using $o(n)$ space cannot distinguish streams where almost every constraint is satisfiable from streams where no ordering beats the random ordering by a noticeable amount. This space bound is tight up to polylogarithmic factors. In the case of MAS our result shows that for every $ε>0$, MAS is not $(1/2+ε)$-approximable in $o(n)$ space. The previous best inapproximability result, due to Guruswami and Tao (APPROX'19), only ruled out $3/4$-approximations in $o(\sqrt n)$ space.
Our results build on a recent work of Chou, Golovnev, Sudan, Velingker, and Velusamy (STOC'22), who provide a tight, linear-space inapproximability theorem for a broad class of "standard" (i.e., non-ordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. We construct a family of appropriate standard CSPs from any given OCSP, apply their hardness result to this family of CSPs, and then convert back to our OCSP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2105_01782 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Streaming approximation resistance of every ordering CSP Singer, Noah G. Sudan, Madhu Velusamy, Santhoshini Data Structures and Algorithms Computational Complexity An ordering constraint satisfaction problem (OCSP) is defined by a family $\mathcal{F}$ of predicates mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. An instance of Max-OCSP($\mathcal{F}$) on $n$ variables consists of a list of constraints, each consisting of a predicate from $\mathcal{F}$ applied on $k$ distinct variables. The goal is to find an ordering of the $n$ variables that maximizes the number of constraints for which the induced ordering on the $k$ variables satisfies the predicate. OCSPs capture well-studied problems including `maximum acyclic subgraph' (MAS) and "maximum betweenness". In this work, we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) streaming setting, when an instance is presented as a stream of constraints. We show that for every $\mathcal{F}$, Max-OCSP($\mathcal{F}$) is approximation-resistant to $o(n)$-space streaming algorithms, i.e., algorithms using $o(n)$ space cannot distinguish streams where almost every constraint is satisfiable from streams where no ordering beats the random ordering by a noticeable amount. This space bound is tight up to polylogarithmic factors. In the case of MAS our result shows that for every $ε>0$, MAS is not $(1/2+ε)$-approximable in $o(n)$ space. The previous best inapproximability result, due to Guruswami and Tao (APPROX'19), only ruled out $3/4$-approximations in $o(\sqrt n)$ space. Our results build on a recent work of Chou, Golovnev, Sudan, Velingker, and Velusamy (STOC'22), who provide a tight, linear-space inapproximability theorem for a broad class of "standard" (i.e., non-ordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. We construct a family of appropriate standard CSPs from any given OCSP, apply their hardness result to this family of CSPs, and then convert back to our OCSP. |
| title | Streaming approximation resistance of every ordering CSP |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2105.01782 |