Max-Cut with Multiple Cardinality Constraints

Ali Vakilian; Madhusudhan Reddy Pittu; Yury Makarychev

REVIEW 4 major objections 4 minor 25 references

Max-Cut with Multiple Cardinality Constraints

T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that Max-Cut with multiple exact size quotas can be approximated within (0.858 − ε) of optimal in polynomial time whenever the number of quotas is constant.

desk verdict A solid, novel kernel + RT rounding for sparse constrained Max-Cut, but the main proof has a normalization gap that needs fixing, and the hardness reduction needs patching. read the letter →

arxiv 2507.12607 v1 pith:FK273O25 submitted 2025-07-16 cs.DS

Yury Makarychev , Madhusudhan Reddy Pittu , Ali Vakilian This is my paper

classification cs.DS MSC 68W2590C2268Q17

keywords ConstrainedMax-CutcardinalityconstraintsapproximationalgorithmssemidefiniteprogrammingLasserrehierarchycorrelationroundingkernelizationmatroid

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's target is Constrained Max-Cut: choose exactly $k_i$ vertices from each of $c$ given groups so that the number of edges crossing the chosen set is maximized, and show this can be done almost as well as unconstrained Max-Cut. Its main result is a $(0.858-\varepsilon)$-approximation algorithm that runs in polynomial time whenever the number of groups is constant, for every $\varepsilon>0$, even when the chosen set is tiny relative to the graph. That improves the old guarantee for a sparse single cardinality constraint, which was only a little above $1/2$, and extends an earlier $0.858$ result that applied only when the chosen set was a constant fraction of the graph. The paper also proves that deciding whether all edges can be cut is NP-hard when the number of constraints is allowed to grow, and that matroid-constrained Max-Cut has a deterministic $1/2$-approximation.

What carries the argument

Two mechanisms carry the argument. The first is an approximate kernel: within each group the algorithm keeps only the top $O(k_i/\varepsilon)$ highest-degree vertices, merges the rest into a super-vertex, and shows that restricting solutions to this core costs at most a $1-4c\varepsilon$ factor of the optimum. The second is the rounding pipeline: solve a high-level Lasserre SDP (a hierarchy of semidefinite programming relaxations), condition on a few sampled vertices to make the solution $\alpha$-block independent (average mutual information inside each group at most $\alpha$), then apply the bias-preserving correlation-rounding procedure of [RT12], which cuts each edge with probability at least $\alpha_{\mathrm{cc}}$ times its SDP contribution and makes each group's selected count have variance $O(\alpha^{1/12})$. A final random correction replaces a small number of vertices per group to meet the quotas exactly with only an $O(\varepsilon)$ loss.

What would settle it

Construct a small Constrained Max-Cut instance with two groups, solve its Lasserre SDP, enforce $\varepsilon^{60}$-block independence by conditioning, apply the inherited rounding step, and measure the variance of the number of selected vertices in each group over many trials; if the variance is not $O(\varepsilon^5)$ relative to the group size, the correction step cannot restore exact quotas without an $O(\varepsilon)$ cut loss, and Theorems 4 and 5 fail.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is Theorem 5: for every $\varepsilon>0$, there is an algorithm that runs in $O(\min\{k/\varepsilon, n\}^{\mathrm{poly}(c/\varepsilon)} + \mathrm{poly}(n))$ time, where $k=\sum_i k_i$, and returns a feasible solution with cut value at least $(\alpha_{\mathrm{cc}}-\varepsilon)$ times the optimum, where $\alpha_{\mathrm{cc}}\approx 0.858$. The single-constraint special case $c=1$ gives the same guarantee for Max-Cut$_k$ for every $k$, including the sparse regime $k=o(n)$ that previously had only a $1/2+\varepsilon_0$ approximation. The same machinery yields a deterministic $1/2$-approximation for Max-Cut under an arbitrary matroid constraint, and an NP-hardness result for the fully general multi-constraint problem: even deciding whether a feasible cut cuts every edge is hard when the number of constraints is unbounded.

Load-bearing premise

The load-bearing premise is that a rounding procedure that provably works when the whole graph is nearly uncorrelated still works when the graph is made nearly uncorrelated separately inside each group, so that the paper can shrink the graph and round group-by-group without re-proving the procedure's guarantees.

Editorial extensions

If this is right

The sparse regime of a single cardinality constraint gains the $0.858$ approximation, replacing the previous $1/2+\varepsilon_0$ bound for all $k$.
When the number of groups $c$ is constant and $\varepsilon$ is fixed, the algorithm runs in polynomial time, so exact per-group quotas are approximable almost as well as ordinary Max-Cut.
Deciding whether a feasible solution cuts every edge is polynomial-time for constant $c$, quasipolynomial for $c=\mathrm{poly}(\log n)$, and NP-hard for arbitrary $c$.
Matroid Max-Cut, which contains the uniform and partition cases, has a deterministic $1/2$-approximation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A consequence the authors leave implicit: the same kernel-plus-rounding recipe may transfer to other constraint satisfaction problems with exact-size constraints, suggesting that sparse quotas need not force the approximation ratio down to $1/2$.
The NP-hardness result hints at a phase transition in $c$—constant is easy, arbitrary is hard—so locating the exact threshold between $\mathrm{poly}(\log n)$ and $n$ is a natural next question.
A testable extension the paper does not pursue: on low-degree graphs whose optimal cuts use vertices just below the degree cutoff, the kernel's $(1-4c\varepsilon)$ retention bound may be loose, and smaller kernels could be possible.
For matroid Max-Cut the $1/2$ factor may be improvable for partition matroids, since the paper's multi-constraint algorithm already reaches $0.858$ for constant $c$; whether stronger SDP relaxations close the gap is left open.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Real improvement here: the O(k/ε) approximate kernel is genuinely new, and combining it with Raghavendra–Tan correlation rounding gives the first αcc−ε approximation for sparse Max-Cutk and for multiple cardinality constraints. The block-independence definition and the conditioning procedure are a natural and convincing extension. The matroid 0.5-approximation is a clean exercise, correctly attributed to the pipage rounding line. These are worthwhile contributions.

The soft spots, in decreasing order of seriousness. First, the normalization: Step 2(b) of the single-constraint algorithm and the corresponding step in the multi-constraint version claim ]OPT − ε^60 ≥ (1−ε)]OPT from Lemma 18(2). Lemma 18(2) only gives ]OPT ≥ ε·W(eE); the inference needs W(eE) ≥ ε^58. No such bound holds. Concretely, with k=1, ε=0.1, and a perfect matching on n > 2ε−59 vertices, the kernel keeps 10 vertices plus the supervertex, W(eE)=20/n, and ]OPT=2/n. The claimed inequality is false, and the SDP lower bound is vacuous. This affects both Theorem 4 and Theorem 5. The result might still be true in such regimes—in the matching example every feasible solution is near-optimal—but the proof as written does not cover them. A fallback for small surviving edge weight is missing.

Second, Theorem 7's reduction is not a valid instance of Constrained Max-Cut as defined: the star centers are never placed in any part, yet the problem requires V to be partitioned. This is patchable, but as stated it is a gap.

Third, minor: Algorithm 4.1 solves a (3+4c/ε120)-round Lasserre SDP, while Theorem 22 requires 4c²/ε120 + 2 rounds. Likely a typo, but the c vs c² difference should be fixed. Also, in the hardness proof the text says δ(S)=1 where it clearly means all edges are cut; another typo.

The RT rounding black box is used in the way the literature normally uses it; the block-independence extension of Theorem 11 to each block is legitimate, not a hidden assumption.

Who this is for: approximation algorithms people working on SDP hierarchies and graph partitioning. It deserves a serious referee; send it to review, but ask for the normalization gap to be addressed before acceptance.

Referee Report

4 major / 4 minor

Summary. The paper studies Constrained Max-Cut, in which vertices are partitioned into c parts and a solution must select exactly k_i vertices from each part while maximizing the weight of edges crossing the selected set. The main claimed contribution is an (α_cc − ε)-approximation algorithm for c = O(1), where α_cc ≈ 0.858 is the Raghavendra–Tan constant, running in time O(min{k/ε, n}^{poly(c/ε)} + poly(n)). The approach combines an approximate kernel that reduces the instance to O(k/ε) vertices with a Lasserre SDP and the Raghavendra–Tan correlation rounding technique, extended to a new notion of α-block independence. The paper also gives a 0.5-approximation for Max-Cut under an arbitrary matroid base constraint and proves NP-hardness of deciding whether a feasible solution cuts all edges for an arbitrary number of cardinality constraints. The kernel construction and several of the local lemmas are argued in detail, but the proof of the central approximation theorems contains a normalization error, and the multi-constraint algorithm has an internal inconsistency in the SDP round count; the hardness reduction also does not produce instances matching the paper's own definition of the problem.

Significance. If the main results were fully established, this would be a substantial advance: it would extend the near-optimal Raghavendra–Tan approximation from the balanced regime min{k, n−k} = Ω(n) to all cardinality values and to multiple simultaneous cardinality constraints, and the approximate kernel would be a reusable tool for converting sparse cut instances into dense ones. The paper is also careful in attributing the correlation rounding package to [RT12] and in identifying the exact hypotheses inherited from that work. However, the central approximation claim is not currently supported by the proof as written, because of a concrete algebraic error in the normalization of the SDP loss; this affects both Theorem 4 and Theorem 5. The block-independence extension is plausible, but the paper should explicitly verify that the imported Raghavendra–Tan rounding guarantees apply to solutions that are only block-independent rather than globally α-independent. The matroid 0.5-approximation is a nice contribution, and the hardness result, once repaired to fit the formal problem definition, would be a useful complement.

major comments (4)

[Section 3.3, Step 2(b); Section 4.3, Lemma 24] The inference "]OPT − ε^60 ≥ (1−ε)]OPT" is not justified by the cited lemma. Lemma 18(2) states only that ]OPT is at least an ε-fraction of the total edge weight in the kernelized graph eE, i.e., ]OPT ≥ ε·W(eE). The desired inequality requires ]OPT ≥ ε^59, which does not follow. Concretely, take a perfect matching on n vertices with total edge weight normalized to 1, set k=1 and ε=0.1; the kernel keeps 10 vertices plus the supervertex s, so W(eE)=20/n and ]OPT=2/n. For n > 2·10^59 we have ]OPT < ε^59, and the additive loss ε^60 exceeds ]OPT, making the guarantee "SDP value ≥ ]OPT − ε^60" vacuous. The same erroneous step appears in Section 4.3 in the proof of Lemma 23 via Lemma 24. Since this step is used to claim that the conditioned SDP value is at least (1−ε)]OPT ≥ (1−5ε)OPT, the subsequent lower bound on the rounded cut value fails for instances with very small kernelized optimum. A separate argument covering the small-]OPT regime is needed for the proofs of Theorems 4 and 5 to go through.
[Section 4.1, Algorithm 4.1 Step 2(a); Theorem 22] The Lasserre level stated in Algorithm 4.1 is inconsistent with Theorem 22. Theorem 22 with α = ε^60 and ℓ = 2 requires an initial (L+ℓ)-round solution with L = 4c^2/α^2 = 4c^2/ε^120, i.e., a total of 4c^2/ε^120 + 2 rounds. Algorithm 4.1 instead states that the algorithm solves a (3 + 4c/ε^120)-round SDP. This differs both in the factor multiplying c and in the additive constant. As written, the algorithm does not supply the level required by the conditioning theorem it invokes, so the multi-constraint analysis is not supported; this must be corrected.
[Section 5.2, Proof of Theorem 7] The reduction from 3D matching does not produce an instance of Constrained Max-Cut as defined in Definition 1. In Definition 1, the sets V_1, ..., V_c partition all of V and every vertex is subject to exactly one cardinality constraint. In the reduction, the star centers are not assigned to any part V_i and are effectively unconstrained. The completeness and soundness arguments rely on the freedom to place each center either in S or outside S independently of the partition-matroid constraints; no assignment of the centers to parts with prescribed cardinalities reproduces this freedom. Consequently, Theorem 7 is not established for the problem defined in the paper. The proof also writes δ(S)=1 where the decision problem asks for δ(S)=|E|, which is a notational slip but should be fixed.
[Sections 1.2 and 4, use of Raghavendra–Tan rounding] The paper states that Algorithm 5.3 of [RT12] preserves vertex biases, cuts each edge with probability at least α_cc times its SDP contribution, and satisfies the variance bound of Theorem 11, and then applies this package to solutions that are only α-block independent. The concentration part is a direct application of Theorem 11 with W uniform on each block, but the edge-cutting guarantee is imported without explicitly checking whether it holds for solutions that are not globally α-independent. The authors should either cite the exact statement from [RT12] that covers the block-independent case or prove that the rounding guarantee extends; as written, this is an unverified load-bearing assumption.

minor comments (4)

[Appendix B, Lemma 27] In the second case of the proof, the text says "When x + y ≤ 1" but the case is actually x + y ≥ 1; the argument then substitutes x′ = 1−x, y′ = 1−y to reduce to the first case. The typo should be corrected.
[Section 5.2, Proof of Theorem 7] The expression "u ∈ X ∩ Y ∩ Z" should read "u ∈ X ∪ Y ∪ Z", since every element of the three sets imposes a part constraint in the reduction.
[Section 3.3 and Section 4.3] The proofs use the phrase "Assume that the constant hidden in the O-notation is 1 for simplicity". This is acceptable for exposition, but the constants in Chebyshev's inequality and in the final approximation ratio should be tracked more explicitly to avoid any hidden dependence on ε and c in the O(ε) terms.
[Section 1.2] The paper defines α-independence with respect to a distribution W and then uses the same notation for the uniform distribution over a block V_j. This is clear in context, but a sentence explicitly stating that block independence is exactly α-independence with respect to each W_j would help the reader.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation; the central claim imports the external Raghavendra-Tan rounding theorem, and the only self-citation is background.

full rationale

The paper's derivation chain is self-contained with respect to the present authors' own claims: the (αcc − ε) approximation is not obtained by fitting or redefining αcc; αcc ≈ 0.858 is inherited as the approximation factor of Raghavendra–Tan Algorithm 5.3 [RT12], an external published theorem with stated SDP and independence assumptions. The kernel theorems (Theorem 12 and Theorem 14) are proven from cut-function submodularity and degree ordering, not from the conclusion being established. The block-independence extension (Definition 19, Theorem 22) is a new conditional-entropy argument adapted from RT12's conditioning technique, not an import of the theorem being proved. The only self-citation is [GMR+11] in a list of prior Max-Bisection approximations in the introduction; it is background and not load-bearing. The main derivational risk is a quantitative normalization gap: Step 2(b) of Section 3.3 infers ]OPT − ε^60 ≥ (1−ε)]OPT from Lemma 18(2), which only yields ]OPT ≥ ε·W(eE) and does not in general imply ]OPT ≥ ε^59; a similar gap appears in Lemma 24. That is a correctness/quantitative issue, not a circular dependency: the asserted approximation does not reduce by construction to a fitted parameter, a self-citation chain, or a renamed version of its own input.

Assumptions & free parameters 4 free parameters · 4 assumptions · 1 invented entities

The central claims rest on the kernel truncation (a proven theorem with design parameter h=k/epsilon), the imported RT rounding package, and the new block-independence conditioning. No data fitting is involved, so the free-parameter list is limited to hand-chosen algorithm constants.

free parameters (4)

alpha = epsilon^60
Chosen by hand in Algorithms 3.1 and 4.1 to make the rounded cut balance concentrate; drives the Lasserre level O(1/alpha^2) = O(epsilon^{-120}) and the variance O(alpha^{1/12}).
kernel size ratio h = k/epsilon (per group)
The kernel keeps the top k/epsilon vertices by degree; the approximation loss (1-4c epsilon) in Theorems 12 and 14 scales with this choice.
Lasserre level ell = 2
RT Theorem 11 is stated for two-round SDP solutions; the algorithms solve higher levels and condition down to level 2.
SDP round count constants (3, 4, 4c^2) = as stated in Algorithm steps
The constants determine how many conditioning rounds are available; the paper's Algorithm 4.1 states 4c instead of 4c^2, creating an inconsistency.

assumptions (4)

standard math The Lasserre SDP hierarchy has the stated consistency, conditioning and SOS properties (Appendix A).
Used to set up pseudo-distributions and conditioning in Theorems 10 and 22.
domain assumption Raghavendra-Tan's rounding theorems hold: Algorithm 5.3 preserves biases, gives expected cut >= alpha_cc * SDP value, and Theorem 11 bounds balance variance.
Imported from RT12, Sections 1.2 and applied throughout Sections 3-4; not re-proven here.
domain assumption Total edge weight is normalized to 1 and k_i <= |V_i|/2 in multi-constraint instances.
Normalization is WLOG; the k_i bound is part of Definition 1, though noted not to be WLOG for c>1.
ad hoc to paper The NP-hardness reduction assumes the star centers are not subject to any partition constraint, that is, they are omitted from the described parts.
This is a gap in Theorem 7's proof: the centers must belong to some part for a valid Constrained Max-Cut instance.

invented entities (1)

Super vertex s (and s_i)
purpose: Contracts all low-degree vertices outside the kernel so the reduced graph has O(k/epsilon) vertices and the selected set becomes a constant fraction of the vertex set.
An algorithmic gadget used in the kernel construction and in the SDP constraint X_s=0; not a physical or data-driven entity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Max-Cut with Multiple Cardinality Constraints." pith.science (2026). https://pith.science/paper/FK273O25

@misc{pith2026250712607,
  author       = {Pith},
  title        = {Pith review of: Max-Cut with Multiple Cardinality Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FK273O25}},
  note         = {Machine review of arXiv:2507.12607}
}

abstract

We study the classic Max-Cut problem under multiple cardinality constraints, which we refer to as the Constrained Max-Cut problem. Given a graph $G=(V, E)$, a partition of the vertices into $c$ disjoint parts $V_1, \ldots, V_c$, and cardinality parameters $k_1, \ldots, k_c$, the goal is to select a set $S \subseteq V$ such that $|S \cap V_i| = k_i$ for each $i \in [c]$, maximizing the total weight of edges crossing $S$ (i.e., edges with exactly one endpoint in $S$). By designing an approximate kernel for Constrained Max-Cut and building on the correlation rounding technique of Raghavendra and Tan (2012), we present a $(0.858 - \varepsilon)$-approximation algorithm for the problem when $c = O(1)$. The algorithm runs in time $O\left(\min\{k/\varepsilon, n\}^{\poly(c/\varepsilon)} + \poly(n)\right)$, where $k = \sum_{i \in [c]} k_i$ and $n=|V|$. This improves upon the $(\frac{1}{2} + \varepsilon_0)$-approximation of Feige and Langberg (2001) for $\maxcut_k$ (the special case when $c=1, k_1 = k$), and generalizes the $(0.858 - \varepsilon)$-approximation of Raghavendra and Tan (2012), which only applies when $\min\{k,n-k\}=\Omega(n)$ and does not handle multiple constraints. We also establish that, for general values of $c$, it is NP-hard to determine whether a feasible solution exists that cuts all edges. Finally, we present a $1/2$-approximation algorithm for Max-Cut under an arbitrary matroid constraint.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 22 canonical work pages

[1]

Better balance by being biased: A 0.8776-approximation for max bisection

Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Better balance by being biased: A 0.8776-approximation for max bisection. ACM Transactions on Algorithms (TALG) , 13(1):1--27, 2016

work page 2016
[2]

Ageev and Maxim Sviridenko

Alexander A. Ageev and Maxim Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization , 8:307--328, 2004

work page 2004
[3]

Global cardinality constraints make approximating some max-2-csps harder

Per Austrin and Aleksa Stankovi \'c . Global cardinality constraints make approximating some max-2-csps harder. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , 145:24:1--24:17, 2019

work page 2019
[4]

Submodular maximization with cardinality constraints

Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 1433--1452. SIAM, 2014

work page 2014
[5]

Rounding semidefinite programming hierarchies via global correlation

Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In Annual Symposium on Foundations of Computer Science , pages 472--481, 2011

work page 2011
[6]

Parameterized complexity of cardinality constrained optimization problems

Leizhen Cai. Parameterized complexity of cardinality constrained optimization problems. The Computer Journal , 51(1):102--121, 2008

work page 2008
[7]

Optimal pricing in networks with externalities

Ozan Candogan, Kostas Bimpikis, and Asuman Ozdaglar. Optimal pricing in networks with externalities. Operations Research , 60(4):883--905, 2012

work page 2012
[8]

Maximizing a monotone submodular function subject to a matroid constraint

Gruia Calinescu, Chandra Chekuri, Martin P\' a l, and Jan Vondr\' a k. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing , 40(6):1740--1766, 2011

work page 2011

Show all 25 references

[9]

Improved approximation algorithms for MAX k -CUT and MAX BISECTION

Alan Frieze and Mark Jerrum. Improved approximation algorithms for MAX k -CUT and MAX BISECTION . Algorithmica , 18(1):67--81, 1997

1997
[10]

A note on approximating max-bisection on regular graphs

Uriel Feige, Marek Karpinski, and Michael Langberg. A note on approximating max-bisection on regular graphs. Information Processing Letters , 79(4):181--188, 2001

2001
[11]

Semialgebraic proofs and efficient algorithm design

Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic proofs and efficient algorithm design. Foundations and Trends® in Theoretical Computer Science , 14(1-2):1--221, 2019

2019
[12]

Approximation algorithms for maximization problems arising in graph partitioning

Uriel Feige and Michael Langberg. Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithms , 41(2):174--211, 2001

2001
[13]

The RPR^2 rounding technique for semidefinite programs

Uriel Feige and Michael Langberg. The RPR^2 rounding technique for semidefinite programs. Journal of Algorithms , 60(1):1--23, 2006

2006
[14]

On the efficiency of influence-and-exploit strategies for revenue maximization under positive externalities

Dimitris Fotakis and Paris Siminelakis. On the efficiency of influence-and-exploit strategies for revenue maximization under positive externalities. Theoretical Computer Science , 539:68--86, 2014

2014
[15]

Finding almost-perfect graph bisections

Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, and Yuan Zhou. Finding almost-perfect graph bisections. In In Proceedings of Innovations in Computer Science , pages 321--337, 2011

2011
[16]

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM) , 42(6):1115--1145, 1995

1995
[17]

A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems

Eran Halperin and Uri Zwick. A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. Random Structures and Algorithms , 20, 05 2002

2002
[18]

Optimal inapproximability results for MAX-CUT and other 2 -variable CSPs ? SIAM Journal on Computing , 37(1):319--357, 2007

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2 -variable CSPs ? SIAM Journal on Computing , 37(1):319--357, 2007

2007
[19]

A comparison of the sherali-adams, lovász-schrijver, and lasserre relaxations for 0-1 programming

Monique Laurent. A comparison of the sherali-adams, lovász-schrijver, and lasserre relaxations for 0-1 programming. Mathematics of Operations Research , 28(3):470--496, 2003

2003
[20]

A survey on fairness for machine learning on graphs

Charlotte Laclau, Christine Largeron, and Manvi Choudhary. A survey on fairness for machine learning on graphs. arXiv preprint arXiv:2205.05396 , 2022

2022 arXiv
[21]

Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko

Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM Journal on Discrete Mathematics , 23(4):2053--2078, 2010

2010
[22]

The lasserre hierarchy in approximation algorithms

Thomas Rothvo . The lasserre hierarchy in approximation algorithms. Lecture Notes for the MAPSP , pages 1--25, 2013

2013
[23]

Approximating CSPs with global cardinality constraints using SDP hierarchies

Prasad Raghavendra and Ning Tan. Approximating CSPs with global cardinality constraints using SDP hierarchies. In Proceedings of the Symposium on Discrete Algorithms , pages 373--387. SIAM, 2012

2012
[24]

( k, n-k )-max-cut: An O ^ * (2^ p ) -time algorithm and a polynomial kernel

Saket Saurabh and Meirav Zehavi. ( k, n-k )-max-cut: An O ^ * (2^ p ) -time algorithm and a polynomial kernel. Algorithmica , 80:3844--3860, 2018

2018
[25]

A .699 -approximation algorithm for max-bisection

Yinyu Ye. A .699 -approximation algorithm for max-bisection. Mathematical Programming , 90:101--111, 2001

2001

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Better balance by being biased: A 0.8776-approximation for max bisection

Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Better balance by being biased: A 0.8776-approximation for max bisection. ACM Transactions on Algorithms (TALG) , 13(1):1--27, 2016

work page 2016

[2] [2]

Ageev and Maxim Sviridenko

Alexander A. Ageev and Maxim Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization , 8:307--328, 2004

work page 2004

[3] [3]

Global cardinality constraints make approximating some max-2-csps harder

Per Austrin and Aleksa Stankovi \'c . Global cardinality constraints make approximating some max-2-csps harder. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , 145:24:1--24:17, 2019

work page 2019

[4] [4]

Submodular maximization with cardinality constraints

Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 1433--1452. SIAM, 2014

work page 2014

[5] [5]

Rounding semidefinite programming hierarchies via global correlation

Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In Annual Symposium on Foundations of Computer Science , pages 472--481, 2011

work page 2011

[6] [6]

Parameterized complexity of cardinality constrained optimization problems

Leizhen Cai. Parameterized complexity of cardinality constrained optimization problems. The Computer Journal , 51(1):102--121, 2008

work page 2008

[7] [7]

Optimal pricing in networks with externalities

Ozan Candogan, Kostas Bimpikis, and Asuman Ozdaglar. Optimal pricing in networks with externalities. Operations Research , 60(4):883--905, 2012

work page 2012

[8] [8]

Maximizing a monotone submodular function subject to a matroid constraint

Gruia Calinescu, Chandra Chekuri, Martin P\' a l, and Jan Vondr\' a k. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing , 40(6):1740--1766, 2011

work page 2011