An ordering constraint satisfaction problem (OCSP) is defined by a family
F
of predicates mapping permutations on
{
1
,
…
,
k
}
to
{
0
,
1
}
. An instance of Max-OCSP(
F
) on
n
variables consists of ...a list of constraints, each consisting of a predicate from
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
F
, Max-OCSP(
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 & Tao (2019), only ruled out 3/4-approximations in
o
(
n
)
space. Our results build on recent works of Chou et al. (2022b, 2024) 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. Our results are obtained by building a family of appropriate standard CSPs (one for every alphabet size
q
) from any given OCSP and applying their theorem to this family of CSPs. To convert the resulting hardness results for standard CSPs back to our OCSP, we show that the hard instances from this earlier theorem have the following “partition expansion” property with high probability: For every partition of the
n
variables into small blocks, for most of the constraints, all variables are in distinct blocks.
We show that the size of maximum cut in a planar graph with \(m\) edges is at least \(2m/3\). We also show that maximal planar graphs saturate this bound.
We study the problem of fairly allocating a multiset \(M\) of \(m\) indivisible items among \(n\) agents with additive valuations. Specifically, we introduce a parameter \(t\) for the number of ...distinct types of items and study fair allocations of multisets that contain only items of these \(t\) types, under two standard notions of fairness: 1. Envy-freeness (EF): For arbitrary \(n\), \(t\), we show that a complete EF allocation exists when at least one agent has a unique valuation and the number of items of each type exceeds a particular finite threshold. We give explicit upper and lower bounds on this threshold in some special cases. 2. Envy-freeness up to any good (EFX): For arbitrary \(n\), \(m\), and for \(t\le 2\), we show that a complete EFX allocation always exists. We give two different proofs of this result. One proof is constructive and runs in polynomial time; the other is geometrically inspired.
Maximum Constraint satisfaction problems (Max-CSPs) are ubiquitous in computer science and encompass optimization problems such as Max-CUT, Max-DICUT, Max-kSAT, Max-kAND, Max-q-Coloring, Unique ...Games, etc. Roughly, a Max-CSP has the following structure: there are a set of variables and a set of constraints on the variables, and the goal is to assign the variables in a way so as to maximize the number of constraints that can be satisfied. The polynomial time approximability of Max-CSPs has been the focus of intense study in the literature.More recently, there has been a lot of interest to study combinatorial optimization problems like Max-CSPs in massive data settings like the streaming setting where the input data is scanned sequentially by the algorithm and then processed in a very limited space. Prior to our work, Max-CUT was the only Max-CSP that was extensively studied in this setting. Unfortunately, these studies showed that any non-trivial streaming approximation algorithm for Max-CUT must have enough memory to store the entire input! And the question of obtaining a non-trivial approximation streaming algorithm for some Max-CSP that does not store the whole input was left wide open.The central result in this thesis gives a non-trivial polylogarithmic space streaming approximation algorithm for every Max-CSP along with a sharp dichotomy theorem showing that our algorithm is optimal among subpolynomial space "sketching'' algorithms---a special class of streaming algorithms used widely in practice, where the algorithm's output is determined by a small sketch it produces of the input stream, and the sketch itself has the property that the sketch of the concatenation of two streams can be computed from the sketches of the two component streams. The first part of this thesis focuses on Max-DICUT which has emerged as central problem in the study of Max-CSPs in the streaming setting. The second part focuses on the dichotomy theorem and some of its consequences for Max-CSPs.
A constraint satisfaction problem (CSP), \(\textsf {Max-CSP}(\mathcal {F})\) , is specified by a finite set of constraints \(\mathcal {F}\subseteq \lbrace q^k \rightarrow \lbrace 0,1\rbrace \rbrace\) ...for positive integers q and k. An instance of the problem on n variables is given by m applications of constraints from \(\mathcal {F}\) to subsequences of the n variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the (γ ,β)-approximation version of the problem for parameters 0 ≤ β ≤ γ ≤ 1, the goal is to distinguish instances where at least γ fraction of the constraints can be satisfied from instances where at most β fraction of the constraints can be satisfied. In this work, we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family \(\mathcal {F}\) and every β < γ, we show that either a linear sketching algorithm solves the problem in polylogarithmic space or the problem is not solvable by any sketching algorithm in \(o(\sqrt {n})\) space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of q=k=2, where we get a dichotomy, and the case when the satisfying assignments of the constraints of \(\mathcal {F}\) support a distribution on \(q^k\) with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables q = 2, binary constraints k =2, and singleton families \(|\mathcal {F}|=1\) and only considered the setting where constraints are placed on literals rather than variables. Our positive results show wide applicability of bias-based algorithms used previously by 47 and 41, which we extend to include richer norm estimation algorithms, by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of 56, which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. In particular, previous works used Fourier analysis over the Boolean cube to initiate their results and the results seemed particularly tailored to functions on Boolean literals (i.e., with negations). Our techniques surprisingly allow us to get to general q-ary CSPs without negations by appealing to the same Fourier analytic starting point over Boolean hypercubes.
A constraint satisfaction problem (CSP), \(\textsf{Max-CSP}(\mathcal{F})\), is specified by a finite set of constraints \(\mathcal{F} \subseteq \{q^k \to \{0,1\}\}\) for positive integers \(q\) and ...\(k\). An instance of the problem on \(n\) variables is given by \(m\) applications of constraints from \(\mathcal{F}\) to subsequences of the \(n\) variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the \((\gamma,\beta)\)-approximation version of the problem for parameters \(0 \leq \beta < \gamma \leq 1\), the goal is to distinguish instances where at least \(\gamma\) fraction of the constraints can be satisfied from instances where at most \(\beta\) fraction of the constraints can be satisfied. In this work we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family \(\mathcal{F}\) and every \(\beta < \gamma\), we show that either a linear sketching algorithm solves the problem in polylogarithmic space, or the problem is not solvable by any sketching algorithm in \(o(\sqrt{n})\) space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of \(q=k=2\), where we get a dichotomy, and the case when the satisfying assignments of the constraints of \(\mathcal{F}\) support a distribution on \(q^k\) with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables \(q=2\), binary constraints \(k=2\), singleton families \(|\mathcal{F}|=1\) and only considered the setting where constraints are placed on literals rather than variables.
We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an explicit constant ...\alpha , s.t. for any \epsilon > 0 (i) there is an ( \alpha-\epsilon )-streaming approximation using space O(\log n) ; and (ii) any ( \alpha+\epsilon )-streaming approximation requires space \Omega(\sqrt{n}) . This generalizes the celebrated work of Kapralov, Khanna, Sudan SODA 2015; Kapralov, Krachun STOC 2019, who showed that the optimal approximation ratio for Max-CUT was 1/2. Prior to this work, the problem of determining this ratio was open for all other Max-2CSPs. Our results are quite surprising for some specific Max-2CSPs. For the Max-DICUT problem, there was a gap between an upper bound of 1/2 and a lower bound of 2/5 Guruswami, Velingker, Velusamy APPROX 2017. We show that neither of these bounds is tight, and the optimal ratio for Max-DICUT is 4/9. We also establish that the tight approximation for Max-2SAT is \sqrt{2}/2 , and for Exact Max-2SAT it is 3/4. As a byproduct, our result gives a separation between space-efficient approximations for Max-2SAT and Exact Max-2SAT. This is in sharp contrast to the setting of polynomial-time algorithms with polynomial space, where the two problems are known to be equally hard to approximate. Finally, we prove that the tight streaming approximation for \text{Max}-k\text{SAT} is \sqrt{2}/2 for every k\geq 2 .
We give an \(\widetilde{O}(\sqrt{n})\)-space single-pass \(0.483\)-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on \(n\) vertices. ...This improves over an \(O(\log n)\)-space \(4/9 < 0.45\) approximation algorithm due to Chou, Golovnev, and Velusamy (FOCS 2020), which was known to be optimal for \(o(\sqrt{n})\)-space algorithms. Max-DICUT is a special case of a constraint satisfaction problem (CSP). In this broader context, we give the first CSP for which algorithms with \(\widetilde{O}(\sqrt{n})\) space can provably outperform \(o(\sqrt{n})\)-space algorithms. The key technical contribution of our work is development of the notions of a first-order snapshot of a (directed) graph and of estimates of such snapshots. These snapshots can be used to simulate certain (non-streaming) Max-DICUT algorithms, including the "oblivious" algorithms introduced by Feige and Jozeph (Algorithmica, 2015), who showed that one such algorithm achieves a 0.483-approximation. Previous work of the authors (SODA 2023) studied the restricted case of bounded-degree graphs, and observed that in this setting, it is straightforward to estimate the snapshot with \(\ell_1\) errors and this suffices to simulate oblivious algorithms. But for unbounded-degree graphs, even defining an achievable and sufficient notion of estimation is subtle. We describe a new notion of snapshot estimation and prove its sufficiency using careful smoothing techniques, and then develop an algorithm which sketches such an estimate via a delicate process of intertwined vertex- and edge-subsampling. Prior to our work, the only streaming algorithms for any CSP on general instances were based on generalizations of the \(O(\log n)\)-space algorithm for Max-DICUT, and thus our work opens the possibility of a new class of algorithms for approximating CSPs.
An ordering constraint satisfaction problem (OCSP) is given by a positive integer \(k\) and a constraint predicate \(\Pi\) mapping permutations on \(\{1,\ldots,k\}\) to \(\{0,1\}\). Given an instance ...of OCSP\((\Pi)\) on \(n\) variables and \(m\) constraints, the goal is to find an ordering of the \(n\) variables that maximizes the number of constraints that are satisfied, where a constraint specifies a sequence of \(k\) distinct variables and the constraint is satisfied by an ordering on the \(n\) variables if the ordering induced on the \(k\) variables in the constraint satisfies \(\Pi\). OCSPs capture natural problems including "Maximum acyclic subgraph (MAS)" and "Betweenness". In this work we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) streaming setting, where an instance is presented as a stream of constraints. We show that for every \(\Pi\), OCSP\((\Pi)\) is approximation-resistant to \(o(n)\)-space streaming algorithms. This space bound is tight up to polylogarithmic factors. In the case of MAS our result shows that for every \(\epsilon>0\), MAS is not \(1/2+\epsilon\)-approximable in \(o(n)\) space. The previous best inapproximability result only ruled out a \(3/4\)-approximation in \(o(\sqrt n)\) space. Our results build on recent works of Chou, Golovnev, Sudan, Velingker, and Velusamy who show tight, linear-space inapproximability results for a broad class of (non-ordering) constraint satisfaction problems over arbitrary (finite) alphabets. We design a family of appropriate CSPs (one for every \(q\)) from any given OCSP, and apply their work to this family of CSPs. We show that the hard instances from this earlier work have a particular "small-set expansion" property. By exploiting this combinatorial property, in combination with the hardness results of the resulting families of CSPs, we give optimal inapproximability results for all OCSPs.
PDF