PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies

Prasad Raghavendra, Ning Tan

arXiv:1110.1064v1cs.DS

TL;DR

CSPs with global cardinality constraints are not well handled by existing approximation and hardness frameworks, and include problems such as Max Bisection. This paper uses Lasserre SDP hierarchies to develop algorithms and a generic conversion from integrality gaps to dictatorship tests. Its Max Bisection algorithm achieves a 0.85 −δ approximation, while the test preserves completeness and soundness up to O(ε + δ) but does not yet yield a corresponding hardness result.

  • Problem

    Existing SDP-based approximation and hardness frameworks do not extend satisfactorily to CSPs with global cardinality constraints, which include Max Bisection and related problems.

    Source: §1 · p. 3

  • Method

    The paper develops a Lasserre-hierarchy approach, including rounding globally uncorrelated SDP solutions and converting integrality-gap instances into dictatorship tests.

    Source: §1.1 · pp. 5–6, §4 · p. 11

  • Results

    0.85 −δ is the algorithm's guaranteed fraction of optimal Max Bisection value, and the test's completeness and soundness differ from the SDP and integral values by O(ε + δ).

    Source: §1.1 · pp. 5–6

  • Takeaways & Limitations

    The integrality-gap-to-test conversion applies to every CSP with cardinality constraints, although the paper presents Max Bisection as its exposition case.

    Source: §1.1 · p. 6

    The dictatorship test does not yet yield a corresponding Max Bisection hardness result because the standard Unique Games framework does not apply to its global constraint.

    Source: §1.1 · p. 6

Abstract

from arXiv · show

This work is concerned with approximating constraint satisfaction problems (CSPs) with an additional global cardinality constraints. For example, \maxcut is a boolean CSP where the input is a graph $G = (V,E)$ and the goal is to find a cut $S \cup \bar S = V$ that maximizes the numberof crossing edges, $|E(S,\bar S)|$. The \maxbisection problem is a variant of \maxcut with an additional global constraint that each side of the cut has exactly half the vertices, i.e., $|S| = |V|/2$. Several other natural optimization problems like \minbisection and approximating Graph Expansion can be formulated as CSPs with global constraints. In this work, we formulate a general approach towards approximating CSPs with global constraints using SDP hierarchies. To demonstrate the approach we present the following results: Using the Lasserre hierarchy, we present an algorithm that runs in time $O(n^{poly(1/\epsilon)})$ that given an instance of \maxbisection with value $1-\epsilon$, finds a bisection with value $1-O(\sqrt{\epsilon})$. This approximation is near-optimal (up to constant factors in $O()$) under the Unique Games Conjecture. By a computer-assisted proof, we show that the same algorithm also achieves a 0.85-approximation for \maxbisection, improving on the previous bound of 0.70 (note that it is \uniquegames hard to approximate better than a 0.878 factor). The same algorithm also yields a 0.92-approximation for \maxtwosat with cardinality constraints. For every CSP with a global cardinality constraints, we present a generic conversion from integrality gap instances for the Lasserre hierarchy to a {\it dictatorship test} whose soundness is at most integrality gap. Dictatorship testing gadgets are central to hardness results for CSPs, and a generic conversion of the above nature lies at the core of the tight Unique Games based hardness result for CSPs. \cite{Raghavendra08}

1 Introduction

Global cardinality constraints make CSPs harder to handle with existing SDP approximation and hardness frameworks, despite their relevance to problems such as Max Bisection. The paper develops a Lasserre-hierarchy approach, giving improved Max Bisection approximations and a gap-to-dictatorship-test conversion, though the test does not yet yield a corresponding Max Bisection hardness result.

1 Introduction

  • Global cardinality constraints fall outside the locality assumptions of standard CSP approximation and hardness frameworks, and variants with even one such constraint remain poorly understood.The paper identifies Max Bisection, Min Bisection, and Small-Set Expansion as examples.Source: §1 · p. 3
  • 0.7027 was the best known Max Bisection approximation factor, while the natural SDP could have value 1 even when every bisection cuts less than 0.95 of the edges.Max Cut, without the balance constraint, has a 0.878 approximation factor.Source: §1 · pp. 3–4

1.1 Our Results

  • The paper develops a general Lasserre-hierarchy approach for approximating CSPs with global cardinality constraints.Source: §1.1 · p. 5
  • 0.85 −δ is the guaranteed fraction of the optimal Max Bisection value achieved by an algorithm running in time O(n^poly(1/δ)).Source: §1.1 · p. 5
  • The algorithm also generalizes to α-Max Cut and weighted Max Bisection, and yields approximations for Min Bisection and α-Balanced Separator.For weighted Max Bisection, the two sides have approximately half the total weight each.Source: §1.1 · pp. 5–6
  • For every CSP with cardinality constraints, a Lasserre integrality-gap instance can be converted into a dictatorship test whose completeness and soundness are within O(ε + δ) of the SDP and integral values.The result is stated generally, with Max Bisection used for exposition.Source: §1.1 · p. 6
  • The resulting dictatorship test does not yet provide a Max Bisection hardness result because the standard Unique Games framework does not apply to its global constraint.The paper points to stronger assumptions, such as Unique Games with expansion or the Small Set Expansion hypothesis.Source: §1.1 · pp. 6–7

2 Overview of Techniques

The overview identifies global correlation as the obstacle to using Max Cut rounding for Max Bisection: an expected half-size cut need not be concentrated near half-size. It uses Lasserre conditioning to reduce correlations, then rounds so each vertex’s bias is preserved.

2 Overview of Techniques

  • For Max Bisection, Goemans–Williamson would give a 0.878-approximation if returned-partition balance were concentrated around its expectation, but highly correlated vertex values mean it need not be.Source: §2 · p. 7
  • Lasserre solutions provide consistent local distributions on small vertex subsets and permit conditioning on assignments, even though a single global distribution need not exist.Conditioning on a partial assignment produces a lower-round Lasserre solution.Source: §2 · pp. 7–8
  • The method measures pairwise dependence with mutual information and calls a solution α-independent when the average mutual information between vertex pairs is at most α.The variables are sampled from the pair’s local distribution associated with the Lasserre SDP.Source: §2 · p. 8
  • Repeatedly conditioning on a vertex’s value reduces average entropy until the solution is α-independent; the rounding then preserves each vertex’s bias so the expected global balance is maintained.The overview says the process reaches α-independence after at most 1/α conditionings, while the rounding scheme is chosen to output balanced cuts in expectation.Source: §2 · p. 8

3 Preliminaries

The preliminaries define CSPs with global cardinality constraints through local payoff functions and target value proportions, and describe Lasserre solutions through consistent local marginals and conditioning.

3 Preliminaries

  • A CSP with global cardinality constraints combines bounded-arity payoff functions over a finite domain with a cardinality function specifying the required fraction of variables assigned each value.The definition requires the cardinality function’s values to sum to one.Source: §3 · p. 9
  • Examples include Max and Min Bisection, α-Max Cut, and Edge Expansion, where the constrained set or side has a specified size or weight.The text also notes that the techniques generalize to weighted cuts with a prescribed fraction of total vertex weight.Source: §3 · p. 9
  • A feasible Lasserre solution has consistent local assignment distributions whose first two moments match vector inner products, and it can be conditioned on a variable’s assignment.The hierarchy enforces global cardinality constraints through variable marginals.Source: §3 · pp. 10–11

4 Globally Uncorrelated SDP Solutions

The section makes Lasserre solutions globally less correlated by conditioning on sampled variable values, then uses the resulting α-independent solution for rounding. It gives an algorithm that finds such a solution while retaining nearly the SDP objective value.

4 Globally Uncorrelated SDP Solutions

  • The conditioning procedure samples variable values from their marginals and conditions the SDP solution until it becomes α-independent.It uses a higher-round Lasserre solution to obtain the desired lower-round solution.Source: §4 · pp. 11–12
  • An SDP solution is α-independent when the average mutual information between vertex pairs, measured using their local pair distribution, is at most α.The pairwise quantity is well-defined even though the SDP variables need not have a joint distribution.Source: §4 · p. 11
  • A sequence of conditionings must reduce average conditional entropy enough to yield a stage with small remaining pairwise conditional mutual information.The section’s lemma bounds the number of conditionings by the available entropy budget, since each variable’s entropy is at most log q.Source: §4 · p. 12
  • For every α and positive integer ℓ, an algorithm finds an α-independent ℓ-round Lasserre solution in time O(n^(poly(1/α)+ℓ)) with objective value at least OPT−α.The procedure starts from a higher-round solution and conditions it while preserving the expected objective value.Source: §4 · pp. 12–13

5 Rounding Scheme for Max Bisection

The rounding scheme combines Lasserre solutions with bias-preserving Gaussian hyperplane rounding and analyzes both cut value and balance. It reports a 0.85–0.86 Max Bisection approximation ratio and a 0.92 approximation for globally constrained Max 2-Sat.

5 Rounding Scheme for Max Bisection

  • The scheme starts from a globally uncorrelated two-round Lasserre solution and is presented as applicable to Max Bisection and other globally constrained CSPs.The associated vectors encode edge payoffs through squared distances, while their components orthogonal to the constant vector capture correlations.Source: §5 · p. 13

5.1 Rounding Scheme

  • The rounding projects a Gaussian vector onto each vertex’s orthogonal component and sets a vertex’s assignment using a threshold chosen to preserve its bias.Preserving individual biases makes the expected balance match the intended value; the analysis separately addresses cut value and balance concentration.Source: §5.1 · p. 14

5.2 Analysis of the Cut Value

  • Numerical techniques show that the rounded cut value is at least 0.85 times the SDP optimum.The analysis of an individual edge’s cut probability reduces to an event involving two correlated Gaussians.Source: §5.2 · p. 14

5.3 Analysis of the Balance

  • For an α-independent two-round Lasserre solution, the algorithm returns an O(α^(1/24))-balanced cut with probability at least 1−O(α^(1/24)).The balance deviation is measured as a fraction of the total vertex weights.Source: §5.3 · pp. 15–16

5.4 Wrapping Up

  • The algorithm’s Max Bisection approximation ratio is between 0.85 and 0.86, and it achieves 0.92 for globally constrained Max 2-Sat.The Max Bisection ratio is established by a computer-assisted proof.Source: §5.4 · pp. 16–17

6 Dictatorship Tests from Globally Uncorrelated SDP Solutions

The section constructs a dictatorship test for Max Bisection from a globally uncorrelated two-round Lasserre SDP solution. Dictator cuts are balanced and retain value close to the SDP value, while soundness concerns balanced cuts far from every dictator.

Unweighting

  • A bisection of the weighted test can be converted to a bisection of an unweighted graph with value DICT(F) − o_M(1).The conversion assigns a fraction of each cluster according to F and then corrects the partition to a bisection, up to rounding errors.Source: §6 · pp. 17–18

Soundness

  • Soundness measures the value of balanced cuts far from every dictator, with distance formalized using influences.The section uses low-influence balanced cuts in its soundness analysis and applies a rounding scheme to the SDP solution.Source: §6 · pp. 18, 20, 21

Construction

  • The test is built from a globally uncorrelated feasible two-round Lasserre solution, with a dictatorship test constructed from the graph and SDP solution.The section describes the test graph on the hypercube and samples edges using vertex-pair assignments, then perturbs coordinates.Source: §6 · pp. 19–20

Completeness

  • Dictator cuts are bisections whose value is within 2ε of the SDP value.The construction's completeness analysis also uses the SDP balance condition to establish that dictator cuts are balanced.Source: §6 · pp. 20–21

Balance analysis

  • For a δ-independent SDP solution, the variance of the rounded cut's balance is at most C(R) poly(δ).The analysis uses this bound to establish concentration of the returned cut's balance around its expectation.Source: §6 · pp. 22–23

A Analysis of Cut Value

This appendix analyzes Algorithm 5.3's cut value by comparing its separation probability with random-hyperplane rounding and deriving a bound for nearby vectors. The analysis also uses a numerical check at a specified threshold.

Analysis strategy

  • The cut-value analysis first compares the rounding algorithm with Goemans–Williamson under certain conditions, then extends the argument by a union-bound-type step.The passage describes the proof strategy for the general case.Source: A Analysis of Cut Value · p. 27

Lemma A.2

  • The function g(t) = e^(t²/2)(1 − μ(t)²), with μ(t) = 2Φ(t) − 1, is decreasing for t ≥ t0.This is stated as Lemma A.2.Source: A Analysis of Cut Value · p. 27

Lemma A.4

  • For vectors with the same bias and nonnegative normalized residual correlation, a random hyperplane separates them with probability at least that of Algorithm 5.3.The comparison applies to unit vectors with the same projection onto I and normalized residual inner product 1 − ρ ≥ 0.Source: A Analysis of Cut Value · p. 28

Numerical verification

  • At t0, the numerical check gives LHS(t0) ≈ 0.8489 and RHS(t0) ≈ 0.836.The appendix uses this check to verify the inequality at t0 after reducing the verification to that threshold.Source: A Analysis of Cut Value · p. 30

Lemma A.5

  • Lemma A.5 gives an upper bound on the probability that Algorithm 5.3 separates unit vectors u and v satisfying ∥u − v∥²/4 ≤ ε.Source: A Analysis of Cut Value · p. 30

B Mutual Information, Statistical Distance and Independence

This appendix relates mutual information to statistical distance, motivated by an explicit bound on the distance between a joint distribution and the product of its marginals. The authors state that their bounds suffice for this work but may be further optimized.

Motivation

  • The section gives an explicit bound on the statistical distance between a joint distribution and the independent distribution, while noting that its parameters could be further optimized.The authors describe these results as sufficient for their use in the paper.Source: B Mutual Information, Statistical… · p. 31

Relation to statistical distance

  • The appendix combines facts about mutual information, Hellinger distance, and Kullback–Leibler divergence to relate mutual information to statistical distance.It introduces the two distances and states facts connecting them before presenting the relation.Source: B Mutual Information, Statistical… · p. 31

Binary variables

  • For jointly distributed {−1, 1}-valued variables, the appendix states a consequence relating covariance to the preceding bounds.The supplied statement does not include the bound's value.Source: B Mutual Information, Statistical… · p. 32
Loading 1110.1064v1…