Pith. sign in

REVIEW 1 major objections 5 minor 46 references

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems

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

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

Pith's one-line read The paper proves that MinCostCSP(Γ) is polynomial-time |D|-approximable whenever the dual discriminator preserves Γ, and that any constant-factor approximation forces a near-unanimity polymorphism unless P = NP.

desk verdict Strong algorithms and a crisp dichotomy, but the unbounded-width hardness leans on a first-power pp-interpretation citation I couldn't confirm. read the letter →

arxiv 2507.08693 v1 pith:KQU4UB2F submitted 2025-07-11 cs.DS cs.CCcs.DM

Ian DeHaan , Neng Huang , Euiwoong Lee This is my paper · ORCID
classification cs.DScs.CCcs.DM MSC 68Q1768W2508A70
keywords minimumcostCSPconstant-factorapproximationpolymorphismnear-unanimityoperationdualdiscriminatorboundedwidthhomogeneousalgebrasUniqueGamesConjecture
topics P versus NP
open problems P versus NP
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

MinCostCSP is the optimisation problem of assigning values to variables so that a given set of constraints is satisfied while minimising a per-variable, per-label cost. This paper claims that the constant-factor approximability of MinCostCSP over a fixed constraint language is governed by the algebra of its polymorphisms: with a dual discriminator operation, a |D|-approximation is always achievable in polynomial time; without a conservative near-unanimity operation, no constant-factor approximation exists unless P = NP. These results meet for languages that contain all permutation relations, yielding a full dichotomy: |D|-approximable if a conservative majority polymorphism exists, NP-hard to approximate within any constant factor otherwise. The paper also gives a constrained example showing that, assuming the Unique Games Conjecture, a majority polymorphism alone does not guarantee approximability in general.

What carries the argument

The machinery is the polymorphism clone of Γ, studied through two named operations. The dual discriminator d(x,y,z) returns the majority value among x, y, z when the three are not all distinct, and the first argument otherwise; it is a majority operation, so any language it preserves is 2-decomposable (Theorem 2.10 from [JCC98]), letting the algorithms work with binary (2,3)-minimal instances in which every two-variable partial assignment extends to a third variable. Binary relations preserved by d then have the restricted 0/1/all shapes of Lemma 3.3—products, cross-like unions, and bijective matchings—which is exactly what makes the greedy fixing step and the LP rounding preserve (2,3)-minimality. The hardness side runs on pp-interpretations in the first power, the gadget translation that allows costs of a MinCostCSP instance to be carried into another MinCostCSP instance; the bounded-width characterization [BK14, DK13] says an unbounded-width language first-power pp-interprets affine equations over some finite abelian group, enabling the Nearest Codeword reduction, while without an NU operation a pp-defined relation supplies the hypergraph vertex cover reduction [DGKR05, DKM18].

What would settle it

Run Algorithm 1 or Algorithm 2 on a small, explicitly listed MinCostCSP instance whose language is preserved by the dual discriminator and check whether the returned solution costs more than |D| times the optimum; finding such an instance would refute Theorem 1.1, while exhibiting a polynomial-time constant-factor approximation for any language without a conservative near-unanimity polymorphism would refute Theorem 1.2 unless P = NP.

Watch

Extended reading notes

Core claim

The central claim is a pair of bracketing results. On the algorithmic side, if a finite-domain constraint language Γ is preserved by the dual discriminator operation—the ternary operation that returns the majority label when a majority exists and otherwise the first argument—then every satisfiable MinCostCSP(Γ) instance admits a polynomial-time |D|-approximation, via either a greedy algorithm that fixes variables one at a time and pays at most |D| times the per-iteration optimum, or an LP-rounding algorithm based on the basic linear programming relaxation that discards labels of LP probability below 1/|D|. On the hardness side, if MinCostCSP(Γ) has any constant-factor approximation, then Pol(Γ) must contain a conservative near-unanimity operation, unless P = NP: unbounded-width languages reduce from Nearest Codeword through a first-power pp-interpretation of affine equations over a finite abelian group, while bounded-width languages without an NU polymorphism reduce from k-uniform hypergraph vertex cover. For languages containing all permutation relations the two sides close into a dichotomy (Theorem 1.3). A separate construction, a ternary relation with a conservative majority polymorphism whose MinCostCSP reduces from Min UnCut, shows that the NU condition alone is not sufficient under the Unique Games Conjecture.

Load-bearing premise

All cost-transferring hardness reductions in the paper depend on the cited result that an unbounded-width language can simulate affine relations over a finite abelian group with one domain element per encoded element; if some unbounded-width language needed several elements per encoded element, the known cost translation would break and the constant-factor hardness conclusion for that language would no longer follow from this argument.

Editorial extensions

If this is right

  • In the Boolean domain (|D| = 2), the necessary NU condition is also sufficient, so the paper recovers the Khanna et al. classification of constant-factor approximable MinCostCSPs as 2CNF-definable or IHB languages (Remark 4.15).
  • For any language containing all permutation relations, deciding whether MinCostCSP(Γ) is |D|-approximable reduces to checking whether Pol(Γ) contains a conservative majority operation; otherwise the problem is inapproximable within any constant factor unless P = NP.
  • The greedy algorithm's cost-accounting argument implies the |D| ratio holds for every satisfiable input, not merely for instances whose optimum is large, because the bound compares directly with the true optimum.
  • The UGC-based P_H example means that a complete dichotomy for all languages over domains of size at least 3 cannot stop at the NU test; it must single out a proper subclass of near-unanimity languages.

Reading between the lines

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

  • Editorial extension: the first-power cost-transfer lemma suggests a general recipe for proving inapproximability of other optimization CSPs: any language that first-power pp-interprets an NP-hard MinCostCSP inherits its approximation hardness, so locating first-power interpretations, rather than general ones, may be the right target for future hardness results.
  • Editorial extension: the LP algorithm's threshold 1/|D| is tailored to the dual discriminator; a natural testable conjecture is that for k-ary near-unanimity languages, a similar threshold-based rounding of the basic LP yields a factor depending on D and k, possibly improving the |D| bound for specific languages.
  • Editorial extension: because Theorem 4.20 relies on UGC and only rules out sufficient-NU under that conjecture, an unconditional proof for P_H, or a demonstration that the same hardness follows from a weaker assumption, would sharpen the boundary; conversely, a refutation of UGC would leave open whether there is a larger tractable class.
  • Editorial extension: the paper's combination of Marchenkov's classification with approximation suggests that other clone classifications, for example of homogeneous or conservative clones, may translate directly into approximation dichotomies for MinCostCSP over restricted relation sets.
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.

Referee Report

1 major / 5 minor

Summary. The paper studies the constant-factor approximability of minimum cost constraint satisfaction problems (MinCostCSP) through the universal-algebraic lens. It proves that if a constraint language has the dual discriminator operation as a polymorphism, then MinCostCSP is |D|-approximable in polynomial time; it gives two algorithms, one greedy and one based on the basic LP relaxation. Complementarily, it proves that any language admitting a constant-factor approximation must have a conservative near-unanimity polymorphism unless P = NP, yielding a dichotomy for languages containing all permutation relations. It also gives a UGC-based example of a language with a majority polymorphism that is nonetheless hard to approximate within any constant factor.

Significance. If the results are correct, they substantially advance the algebraic theory of constant-factor approximability for MinCostCSP, extending the DKM18 necessity result for MinCSP and providing a clean dichotomy for a natural generalization of Boolean CSPs with variable negation. The algorithmic part is elegant: the greedy charging argument in Theorem 3.11 and the LP threshold argument in Theorem 3.12 are self-contained and sound. The hardness arguments are reductions from Nearest Codeword and hypergraph vertex cover, following the DKM18 framework. The paper is proof-based, with no fitting parameters, and the main claims are falsifiable in the usual sense. The principal caveat is the precise provenance of the first-power pp-interpretation theorem used in the unbounded-width hardness case.

major comments (1)
  1. [§4.2, Theorem 4.6 and Lemma 4.12] The unbounded-width half of the proof of Theorem 1.2 rests entirely on Theorem 4.6, which asserts that every language without bounded width pp-interprets the affine relations of a nontrivial finite abelian group in the first power, using pp-definitions without equality. This exact first-power, equality-free formulation is load-bearing: as the authors themselves note in Section 4.1, cost translation in Lemma 4.5 is straightforward only for n = 1, and there is no natural translation for n ≥ 2. The cited sources [BK14, DK13] are not pinpointed to a specific theorem or page, and the bounded-width characterization is often stated in the literature in terms of pp-constructions or pp-interpretations with powering. Please supply the precise theorem statement and location in [BK14, DK13], or a proof of the first-power claim. If only a power-n version is available, then Lemma 4.12 does not go through, and the necessity of a conservative near-unanimity polymorphism for constant-factor approximability is not established by the argument as written.
minor comments (5)
  1. [§4.1, Lemma 4.5 proof] In the proof of Lemma 4.5, the sentence 'so we add (the constraints and the auxiliary variables of) this instance to I2' should refer to I1, not I2.
  2. [§1, Introduction] The text refers to 'Schaffer [Sch78]'; the reference is to Thomas J. Schaefer, so the name should be spelled 'Schaefer'.
  3. [§4.1 and §4.2] There are several typographical slips: 'pp-interpretes' should be 'pp-interprets', 'Barto el al.' should be 'Barto et al.', and 'condtion' should be 'condition'.
  4. [§3.2, Algorithm 1] The notation 'tend' in Observations 3.7 and 3.8 is informal; please use a clearer notation such as t_end or t^end to denote the final values of t.
  5. [§4.2, Theorem 4.6] Even if the first-power statement is correct, Theorem 4.6 should carry a precise citation to a numbered theorem in [BK14] or [DK13], since the formulation is unusually specific and is central to the hardness proof.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: central results are derived from external theorems and explicit credit, with no fitted-input predictions or self-citation chain.

full rationale

The paper is a proof-based theory paper with no parameters fitted to data and no prediction defined in terms of a fitted quantity. Its central algorithmic claim (Theorem 1.1) follows from (2,3)-minimality, the dual-discriminator relation classification (Lemma 3.3), and a charging argument; none of these steps assumes the target theorem. The hardness half (Theorem 1.2/4.1) is built on external results: the bounded-width characterization of Barto-Kozik and Dalmau-Krokhin (Theorem 4.6), the hardness of Nearest Codeword and hypergraph vertex cover, and the DKM18 approach, which the paper explicitly credits: 'We note that Dalmau et al. [DKM18] obtained a similar necessary condtion for the problem of MinCSP. We will closely follow their proof.' The load-bearing first-power pp-interpretation condition is imported from cited external work, not from the authors' own prior results, so any concern that Theorem 4.6 is stronger than what the cited sources prove is a correctness/verification risk, not circularity. The paper even flags the honest limitation that 'there seems to be no natural way of doing this if we are using a pp-interpretation with n ≥ 2,' which further confirms that the reduction is not hiding an assumption inside its own definitions. Section 4.3 uses the external UGC-based Min UnCut hardness of KKMO07, and Section 5 applies the Marchenkov/Szendrei/Dalmau classifications. No identified step reduces by construction to its own inputs, and no load-bearing self-citation chain is present. The appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 10 assumptions · 0 invented entities

The paper is fully theorem/proof based. There are no fitted parameters and no posited entities; the free-parameters and invented-entities ledgers are empty. Threshold choices inside algorithms (e.g., the 1/|D| LP cutoff in Algorithm 2) are design decisions proven sufficient, not fitted parameters. Every result is derived from external, established theorems (bounded-width hierarchy, homogeneous clone classification, known hardness results) plus the paper's own self-contained arguments, under the explicitly stated assumptions P ≠ NP and, for the counterexample, UGC. The heaviest external load is the first-power, equality-free form of the bounded-width pp-interpretation theorem, which is what makes the cost-preserving reductions possible.

assumptions (10)
  • domain assumption P ≠ NP
    All hardness results (Theorems 1.2, 1.3, Lemmas 4.12, 4.14, and the refutation of [RRS19]) assume P ≠ NP, the standard complexity hypothesis stated in each theorem.
  • domain assumption Unique Games Conjecture (UGC)
    Theorem 4.20's inapproximability of MinCostCSP(PH) and the resulting failure of NU-sufficiency use the KKMO07 hardness of Min UnCut, which is conditional on UGC. The paper states this conditionality throughout.
  • standard math Bounded-width characterization (Theorem 4.6, from [BK14, DK13])
    Lemma 4.12 needs that every unbounded-width language pp-interprets Γ(G) of a nontrivial finite abelian group in the first power, without equality. The first-power form is essential because the cost-preserving reduction (Lemma 4.5) works only for n = 1.
  • standard math Barto's bounded-width tractability (Theorem 3.2, [Bar14])
    Both the greedy and LP algorithms terminate by finding satisfying assignments in nontrivial (2,3)-minimal instances whose language has bounded width; this is Theorem 3.2, cited and used as a black box.
  • standard math NU implies k-decomposability (Theorem 2.10, [JCC98])
    Section 3 uses 2-decomposability of dual-discriminator languages to reduce arbitrary instances to binary instances before applying the algorithms.
  • standard math DKM18's bounded-width no-NU lemma (Lemma 4.13, [DKM18])
    Lemma 4.14 inherits from DKM18 the fact that bounded-width languages without NU pp-define the k-uniform hypergraph vertex cover relation R_k = {0,1}^k \ {(0,...,0)}.
  • standard math Marchenkov/Szendrei classification of homogeneous algebras (Theorem 5.7, [Sze86])
    The permutation-language dichotomy (Theorem 5.2) depends on this classification of clones of homogeneous algebras, including the assertion that the Klein 4-group is the only small-domain exception.
  • standard math Hardness of Nearest Codeword (Theorem 4.9, [DMS03, CW12])
    Corollary 4.11 and Lemma 4.12 base the unbounded-width hardness on the NP-hardness of approximating Nearest Codeword within 2^{log^{1-ε}(n)}.
  • standard math Hardness of k-uniform hypergraph vertex cover (Theorem 4.10, [DGKR05])
    Lemma 4.14 uses the k-1-ε inapproximability of k-uniform hypergraph vertex cover; since k can be taken arbitrarily large, no constant factor survives.
  • standard math KKMO07 UGC-hardness of Min UnCut (Theorem 4.19, [KKMO07])
    Theorem 4.20's reduction from Min UnCut inherits its UGC-hardness from KKMO07.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems." pith.science (2026). https://pith.science/paper/KQU4UB2F

@misc{pith2026250708693,
  author       = {Pith},
  title        = {Pith review of: On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KQU4UB2F}},
  note         = {Machine review of arXiv:2507.08693}
}
abstract

We study minimum cost constraint satisfaction problems (MinCostCSP) through the algebraic lens. We show that for any constraint language $\Gamma$ which has the dual discriminator operation as a polymorphism, there exists a $|D|$-approximation algorithm for MinCostCSP$(\Gamma)$ where $D$ is the domain. Complementing our algorithmic result, we show that any constraint language $\Gamma$ where MinCostCSP$(\Gamma)$ admits a constant-factor approximation must have a \emph{near-unanimity} (NU) polymorphism unless P = NP, extending a similar result by Dalmau et al. on MinCSPs. These results imply a dichotomy of constant-factor approximability for constraint languages that contain all permutation relations (a natural generalization for Boolean CSPs that allow variable negation): either MinCostCSP$(\Gamma)$ has an NU polymorphism and is $|D|$-approximable, or it does not have any NU polymorphism and is NP-hard to approximate within any constant factor. Finally, we present a constraint language which has a majority polymorphism, but is nonetheless NP-hard to approximate within any constant factor assuming the Unique Games Conjecture, showing that the condition of having an NU polymorphism is in general not sufficient unless UGC fails.

Figures

Figures reproduced from arXiv: 2507.08693 by the authors.

Figure 1
Figure 1. BLP relaxation for MinCostCSP(Γ) problem. We remark that in polynomial time we can actually enforce the marginal consistency requirement on any constant-sized set of variables, and thus obtain tighter relaxations on the so-called Sherali-Adams hierarchy ([SA90]). However, this will not be needed for our purpose. For any MinCostCSP instance I, let LP(I) be the optimal value of the BLP relaxation for I. Our LP￾based a… view at source ↗
Figure 2
Figure 2. The undirected graph H corresponding to PH. We now verify that PH is preserved by a conservative majority operation. Claim 4.17. Let f : A3 → A be defined as follows f(a1, a2, a3) =  a if |{i ∈ [3] | ai = a}| ≥ 2, 2 otherwise. 16 [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
Figure 3
Figure 3. The reduction from Min UnCut to MinCostCSP(PH). The nonzero costs are c(x, 2) = c(y, 2) = 1, c(ze, 2) = c(z ′ e , 2) = we. Then f ∈ Pol(PH). Proof. Let (a1, b1),(a2, b2),(a3, b3) ∈ PH. We need to verify that (f(a1, a2, a3), f(b1, b2, b3)) ∈ PH. This is always true if at least one of f(a1, a2, a3) and f(b1, b2, b3) is 2. If neither is 2, then there is a majority in (a1, a2, a3) as well as in (b1, b2, b3). It follows … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 45 canonical work pages

  1. [1]

    The dichotomy for conservative constraint satisfaction problems revisited

    Libor Barto. The dichotomy for conservative constraint satisfaction problems revisited. In 2011 IEEE 26th Annual Symposium on Logic in Computer Science , pages 301--310. IEEE, 2011

    work page 2011

  2. [2]

    The collapse of the bounded width hierarchy

    Libor Barto. The collapse of the bounded width hierarchy. Journal of Logic and Computation , 26(3):923--943, 2014

    work page 2014

  3. [3]

    On the mysteries of max nae-sat

    Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick. On the mysteries of max nae-sat. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 484--503. SIAM, 2021

    work page 2021

  4. [4]

    Separating max 2-and, max di-cut and max cut

    Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick. Separating max 2-and, max di-cut and max cut. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 234--252. IEEE, 2023

    work page 2023

  5. [5]

    Inapproximability of hypergraph vertex cover and applications to scheduling problems

    Nikhil Bansal and Subhash Khot. Inapproximability of hypergraph vertex cover and applications to scheduling problems. In International Colloquium on Automata, Languages, and Programming , pages 250--261. Springer, 2010

    work page 2010

  6. [6]

    Constraint satisfaction problems solvable by local consistency methods

    Libor Barto and Marcin Kozik. Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM (JACM) , 61(1):1--19, 2014

    work page 2014

  7. [7]

    Galois theory for post algebras

    VG Bondarchuk, LA Kaluzhnin, VN Kotov, and BA Romov. Galois theory for post algebras. i-ii. Kibernetika , 3:1--10, 1969

    work page 1969

  8. [8]

    Polymorphisms, and How to Use Them

    Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and How to Use Them . In Andrei Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability , volume 7 of Dagstuhl Follow-Ups , pages 1--44. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, Dagstuhl, Germany, 2017

    work page 2017

Show all 46 references
  1. [9]

    Polynomial interpolation and the chinese remainder theorem for algebraic systems

    Kirby A Baker and Alden F Pixley. Polynomial interpolation and the chinese remainder theorem for algebraic systems. Mathematische Zeitschrift , 143:165--174, 1975

    1975

  2. [10]

    Andrei A. Bulatov. Tractable conservative constraint satisfaction problems. In 18th Annual IEEE Symposium of Logic in Computer Science, 2003. Proceedings. , pages 321--330. IEEE, 2003

    2003

  3. [11]

    Andrei A. Bulatov. Conservative constraint satisfaction re-revisited. Journal of Computer and System Sciences , 82(2):347--356, 2016

    2016

  4. [12]

    A dichotomy theorem for nonuniform csps

    Andrei A Bulatov. A dichotomy theorem for nonuniform csps. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 319--330. IEEE, 2017

    2017

  5. [13]

    Cooper, David A

    Martin C. Cooper, David A. Cohen, and Peter G. Jeavons. Characterising tractable constraints. Artificial Intelligence , 65(2):347--361, 1994

    1994

  6. [14]

    A deterministic reduction for the gap minimum distance problem

    Qi Cheng and Daqing Wan. A deterministic reduction for the gap minimum distance problem. IEEE Transactions on Information Theory , 58(11):6935--6941, 2012

    2012

  7. [15]

    A new tractable class of constraint satisfaction problems

    Victor Dalmau. A new tractable class of constraint satisfaction problems. Annals of Mathematics and Artificial Intelligence , 44:61--85, 2005

    2005

  8. [16]

    A new multilayered pcp and the hardness of hypergraph vertex cover

    Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev. A new multilayered pcp and the hardness of hypergraph vertex cover. SIAM Journal on Computing , 34(5):1129--1146, 2005

    2005

  9. [17]

    Robust satisfiability for csps: Hardness and algorithmic results

    V \' ctor Dalmau and Andrei Krokhin. Robust satisfiability for csps: Hardness and algorithmic results. ACM Transactions on Computation Theory (TOCT) , 5(4):1--25, 2013

    2013

  10. [18]

    Robust algorithms with polynomial loss for near-unanimity csps

    V \' ctor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, and Jakub Oprsal. Robust algorithms with polynomial loss for near-unanimity csps. SIAM Journal on Computing , 48(6):1763--1795, 2019

    2019

  11. [19]

    Towards a characterization of constant-factor approximable finite-valued csps

    V \' ctor Dalmau, Andrei Krokhin, and Rajsekar Manokaran. Towards a characterization of constant-factor approximable finite-valued csps. Journal of Computer and System Sciences , 97:14--27, 2018

    2018

  12. [20]

    Micciancio, and M

    I Dumer, D. Micciancio, and M. Sudan. Hardness of approximating the minimum distance of a linear code. IEEE Transactions on Information Theory , 49(1):22--37, 2003

    2003

  13. [21]

    Local distribution and the symmetry gap: Approximability of multiway partitioning problems

    Alina Ene, Jan Vondrak, and Yi Wu. Local distribution and the symmetry gap: Approximability of multiway partitioning problems. arXiv preprint arXiv:1503.03905 , 2015

    2015 arXiv

  14. [22]

    The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory

    Tom \'a s Feder and Moshe Y Vardi. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing , 28(1):57--104, 1998

    1998

  15. [23]

    Closed systems of functions and predicates

    David Geiger. Closed systems of functions and predicates. Pacific journal of mathematics , 27(1):95--100, 1968

    1968

  16. [24]

    A dichotomy for minimum cost graph homomorphisms

    Gregory Gutin, Pavol Hell, Arash Rafiey, and Anders Yeo. A dichotomy for minimum cost graph homomorphisms. European Journal of Combinatorics , 29(4):900--911, 2008

    2008

  17. [25]

    A bounded approximation for the minimum cost 2-sat problem

    Dan Gusfield and Leonard Pitt. A bounded approximation for the minimum cost 2-sat problem. Algorithmica , 8(1):103--117, 1992

    1992

  18. [26]

    Approximation of minimum cost homomorphisms

    Pavol Hell, Monaldo Mastrolilli, Mayssam Mohammadi Nevisi, and Arash Rafiey. Approximation of minimum cost homomorphisms. In Algorithms--ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings 20 , pages 587--598. Springer, 2012

    2012

  19. [27]

    The dichotomy of minimum cost homomorphism problems for digraphs

    Pavol Hell and Arash Rafiey. The dichotomy of minimum cost homomorphism problems for digraphs. SIAM Journal on Discrete Mathematics , 26(4):1597--1608, 2012

    2012

  20. [28]

    Constraints, consistency and closure

    Peter Jeavons, David Cohen, and Martin C Cooper. Constraints, consistency and closure. Artificial Intelligence , 101(1-2):251--265, 1998

    1998

  21. [29]

    Introduction to the maximum solution problem

    Peter Jonsson and Gustav Nordh. Introduction to the maximum solution problem. Complexity of Constraints: An Overview of Current Research Themes , pages 255--282, 2008

    2008

  22. [30]

    On the power of unique 2-prover 1-round games

    Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages 767--775, 2002

    2002

  23. [31]

    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

  24. [32]

    On lp-based approximability for strict csps

    Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, and Nisheeth K Vishnoi. On lp-based approximability for strict csps. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1560--1573. SIAM, 2011

    2011

  25. [33]

    Vertex cover might be hard to approximate to within 2-

    Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2- . Journal of Computer and System Sciences , 74(3):335--349, 2008

    2008

  26. [34]

    The approximability of constraint satisfaction problems

    Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P Williamson. The approximability of constraint satisfaction problems. SIAM Journal on Computing , 30(6):1863--1920, 2001

    1920

  27. [35]

    The Complexity of Valued CSPs

    Andrei Krokhin and Stanislav Zivny. The Complexity of Valued CSPs . In Andrei Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability , volume 7 of Dagstuhl Follow-Ups , pages 233--266. Schloss Dagstuhl -- Leibniz-Zentrum f \"u...

    2017

  28. [36]

    Marczewski

    E. Marczewski. Homogeneous algebras and homogeneous operations. Fund. Math , 56(8):103, 1964

    1964

  29. [37]

    Marchenkov

    S.S. Marchenkov. Homogeneous algebras. Problemy Kibernetiki , 39:85--106, 1982

    1982

  30. [38]

    E.L. Post. The two-valued iterative systems of mathematical logic. Annals of Mathematics Studies , 1941

    1941

  31. [39]

    Optimal algorithms and inapproximability results for every csp? In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 245--254, 2008

    Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 245--254, 2008

    2008

  32. [40]

    Toward a dichotomy for approximation of h-coloring

    Akbar Rafiey, Arash Rafiey, and Thiago Santos. Toward a dichotomy for approximation of h-coloring. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , pages 91--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2019

    2019

  33. [41]

    A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems

    Hanif D Sherali and Warren P Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics , 3(3):411--430, 1990

    1990

  34. [42]

    The complexity of satisfiability problems

    Thomas J Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing , pages 216--226, 1978

    1978

  35. [43]

    Clones in universal algebra

    \'A gnes Szendrei. Clones in universal algebra . Presses de l'Université de Montréal, 1986

    1986

  36. [44]

    A dichotomy theorem for the general minimum cost homomorphism problem

    Rustem Takhanov. A dichotomy theorem for the general minimum cost homomorphism problem. In 27th International Symposium on Theoretical Aspects of Computer Science (2010) , pages 657--668. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2010

    2010

  37. [45]

    The complexity of finite-valued csps

    Johan Thapper and Stanislav Z ivn \`y . The complexity of finite-valued csps. Journal of the ACM (JACM) , 63(4):1--33, 2016

    2016

  38. [46]

    A proof of the csp dichotomy conjecture

    Dmitriy Zhuk. A proof of the csp dichotomy conjecture. Journal of the ACM (JACM) , 67(5):1--78, 2020

    2020

Pith tools

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