Pith. sign in

REVIEW 4 major objections 4 minor 4 references

Exploiting Structure in the Boolean Weighted Constraint Satisfaction Problem: A Constraint Composite Graph-Based Approach

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

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

Pith's one-line read The paper's central claim is that the constraint composite graph (CCG) turns every Boolean WCSP into an equivalent minimum weighted vertex cover problem, and that this equivalence is a practical engine for faster solving with better…

desk verdict Solid application of an existing reduction with two genuinely new pieces; the load-bearing positive-term gadget is not proved, and the experiments are thinner than the claims. read the letter →

arxiv 2608.10005 v1 pith:ITGOL3AI submitted 2026-08-07 cs.LO physics.comp-ph

Hong Xu This is my paper · ORCID
classification cs.LOphysics.comp-ph MSC 05C6968Q2568R1090C27
keywords constraintcompositegraphBooleanweightedsatisfactionproblemminimumvertexcoverNemhauser-Trotterreductionmin-summessagepassingintegerlinearprogrammingencodingquantumannealingnon-Booleanvariableencodings
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

This dissertation hypothesizes that the constraint composite graph (CCG) can help a general-purpose Boolean WCSP solver discover the structure of its input and solve it faster and with better guarantees. The CCG converts any Boolean WCSP instance into an undirected vertex-weighted graph whose minimum weighted vertex cover encodes the optimal assignment of the original variables. The author shows the conversion is practically usable: it enables the Nemhauser-Trotter reduction to fix variable values before search, gives min-sum message passing solutions closer to optimal, produces an ILP encoding whose constraints contain at most two variables, and supplies a QUBO formulation for quantum annealing. The final chapter extends the CCG to non-Boolean variables with three new encodings and singles out the clique-based encoding for better numerical behavior. A sympathetic reading is that minimum weighted vertex cover becomes a substrate problem for the entire WCSP framework.

What carries the argument

The central object is the constraint composite graph (CCG): an undirected vertex-weighted graph built from the original variables plus auxiliary vertices, in which each weighted constraint is first written as a polynomial and each polynomial term is rendered by a small graph gadget. The identity that carries the argument is that the projection of any minimum weighted vertex cover onto the original variable vertices reproduces the WCSP's optimal assignment, so the WCSP and its CCG are equivalent optimization problems. The CCG is constructible in polynomial time, is always tripartite, and is decomposable constraint-by-constraint; these three properties are what let the later chapters treat kernelization, message passing, integer programming, and annealer embeddings as variations on weighted vertex cover.

What would settle it

Take a Boolean WCSP with a single positive nonlinear constraint such as $w \cdot X_1 X_2 X_3$ with $w = 1$, construct its CCG with a large thorn weight $L > w + 1$, compute an exact MWVC using rational arithmetic, and check whether the projected assignment minimizes the true WCSP over all eight assignments; any mismatch would refute the claimed gadget cancellation. A complementary test is to solve the same CCG in floating point and observe whether the large $L$ changes which cover is selected, which would confirm the numerical-instability path the author himself flags for large-weight gadgets.

Watch

Extended reading notes

Core claim

The central claim, stated as the dissertation's hypothesis, is that the CCG can help algorithms discover structure in the Boolean WCSP and therefore solve it faster and with better theoretical guarantees. The load-bearing assertion is an equivalence: computing a minimum weighted vertex cover on the CCG yields a solution to the original Boolean WCSP. On that foundation the dissertation reports four concrete discoveries: the CCG enables the Nemhauser-Trotter reduction as a polynomial-time kernelization that fixed all variables on about an eighth of the benchmarks; the lifted min-sum message passing algorithm produces significantly better solutions than direct message passing, especially on sparse instances; the CCG-based ILP encoding has at most two variables per constraint and preserves the integrality of the LP relaxation for bipartite MWVC instances; and the CCG-based hybrid quantum-classical algorithm embeds more instances than an ILP-based one. The dissertation also extends the CCG to non-Boolean variables, claiming the binary number-based, direct symmetric, and clique-based encodings dominate the prior high-degree polynomial-based encoding, with the clique-based encoding avoiding very large weights.

Load-bearing premise

The entire chain depends on the positive-nonlinear-term gadget: auxiliary thorn vertices with a very large weight are asserted, but not proved in this dissertation, to cancel lower-order terms exactly when the MWVC is projected back to the variables; if that cancellation is wrong, or if the large weights cause numerical instability in solvers or annealers, the CCG equivalence and all experimental claims built on it would be affected.

Editorial extensions

If this is right

  • The Nemhauser-Trotter reduction, applied to the CCG, fixes the optimal values of a subset of variables in polynomial time before any search, and the dissertation reports it solved about one eighth of the benchmark instances with an empty kernel.
  • The lifted min-sum message passing algorithm, run on the CCG instead of the factor graph, produces solutions at least as close to optimal as the original MSMP on sparse random instances and dramatically better on the benchmark sets.
  • The CCG-based ILP encoding has asymptotically fewer constraints, and at most two variables per constraint, than the direct and improved direct encodings, and it preserves the LP-integrality property for MWVC instances on bipartite graphs.
  • The CCG-based hybrid quantum-classical algorithm works for non-binary Boolean WCSPs where the polynomial-based HQCA does not apply, and it fits onto annealing hardware in cases where the ILP-based HQCA fails to embed.
  • The clique-based non-Boolean encoding, unlike the high-degree polynomial-based encoding, avoids very large gadget weights and is therefore positioned as the most numerically stable extension to non-Boolean variables.

Reading between the lines

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

  • If the CCG equivalence proves robust, then improvements to weighted vertex cover solvers—kernelization, cutting planes, message-passing schedules, and annealer embeddings—should transfer automatically to every WCSP subclass whose CCG inherits the relevant structure.
  • The dissertation itself notes that the CCG does not carry factor-2 approximability from MWVC to the WCSP because the gadget construction introduces constants; a natural next step would be to design gadgets that preserve approximation ratios, which the author does not attempt.
  • Because the author compares the binary number-based and direct symmetric encodings to SAT encodings, an immediate testable extension is to port SAT preprocessing techniques to the CCG construction, using the clique-based encoding as the low-weight target.
  • The NT reduction's role as an implicit local consistency suggests that other MWVC kernelization algorithms, such as crown reductions, could become new WCSP preprocessing methods—an avenue the author lists as future work.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. The dissertation develops the constraint composite graph (CCG) approach to the Boolean weighted constraint satisfaction problem (WCSP). Its central reduction, stated in Section 2.3, is that computing a minimum weighted vertex cover (MWVC) on the CCG of a WCSP instance yields an optimal solution to the WCSP. On this basis, the author presents four applications: the Nemhauser-Trotter reduction as a kernelization procedure (Chapter 3), a lifted min-sum message passing algorithm (Chapter 4), a CCG-based integer linear programming encoding (Chapter 5), and a CCG-based hybrid quantum-classical algorithm for quantum annealing (Chapters 6 and 7). Chapter 7 proposes three new encodings for non-Boolean variables: binary number-based, direct symmetric, and clique-based. The dissertation claims three affirmative answers to its research questions: the CCG has new theoretical properties, it is practically useful, and it extends promisingly to non-Boolean variables. The main theoretical result that is fully proved is the bipartiteness of the CCG for MWVC instances on bipartite graphs in Section 5.4, from which integrality of the corresponding LP relaxation follows. The main practical evidence consists of benchmark experiments on UAI 2014 and an existing WCSP benchmark suite, plus small random instances and two D-Wave experiments.

Significance. If the CCG-to-WCSP reduction is taken as established, the dissertation contributes a useful unifying framework and several concrete algorithmic ideas. The ILP encoding comparison in Section 5.2 gives explicit asymptotic bounds on variables, constraints, and constraint width, and the bipartite preservation result in Section 5.4 is clean and correctly reasoned. The non-Boolean encodings in Chapter 7, especially the clique-based encoding, are interesting and the asymptotic trade-off table (Table 7.1) is a useful reference. The experiments are honest in reporting mixed results, including cases where the improved direct ILP encoding outperforms the CCG-based encoding. However, the central gadget for positive nonlinear terms is not proved in the manuscript, and the experimental support for the practical claims is uneven: the lifted MSMP algorithm converges much less often, and the quantum annealing study is a feasibility demonstration on very small instances. For these reasons the significance of the practical claims is currently conditional on a missing proof and on a more careful experimental accounting.

major comments (4)
  1. [Section 2.3, Figure 2.4(c)] The equivalence that grounds all later chapters, "Computing the MWVC for the CCG yields a solution for the Boolean WCSP," is only fully demonstrated for linear and negative nonlinear terms. For a positive nonlinear term w·(Xi·Xj·Xk), the text states that the flower+thorn projection represents L·(1−Xk) + w − w·(Xi·Xj·(1−Xk)) and then says "By constructing CCG gadgets that cancel out the lower order terms as shown before" without giving the construction or the cancellation calculation. This is load-bearing because every later algorithm inherits the exactness of this reduction, and Section 8.2 explicitly notes that CCG gadgets introduce additive constants that prevent approximation-ratio transfer. Please supply a complete gadget specification and a proof, or an exact rational-arithmetic verification, that for every assignment of the variables the projected MWVC weight equals the desired polynomial term up to the stated additive constant, for arbitrary arity and arbitrary weights.
  2. [Section 7.2.1, Figure 7.2(c)] The same omitted construction appears in the non-Boolean extension. For a positive nonlinear term w·(Y1·...·Ym), the text only states that edges are split by inserting a vertex of large weight L and that "the CCG gadgets for lower-degree terms are recursively constructed (Kumar 2008b)." No proof is given that the projection of the resulting gadget equals the intended expression, nor is the recursive gadget explicitly defined. Since the asymptotic comparisons in Section 7.2.4 and the Chapter 7 experiments depend on the exactness and size of these gadgets, this construction needs to be made precise and verified, or the chapter's claims should be explicitly conditional on the cited construction.
  3. [Section 4.4, Tables 4.1 and 4.2, Figure 4.3] The claim that the lifted MSMP algorithm is practically useful is not fully supported by the reported convergence behavior. Table 4.1 shows that the original MSMP converges on 124 and 44 instances in the two benchmark sets where the lifted MSMP does not converge at all, and only 11 instances are available for the direct convergence-time comparison in Table 4.2. Figure 4.3 and Tables 4.3 and 4.4 compare non-converged, time-limited outputs after 5 minutes or 30 seconds. The paper acknowledges this but still concludes that the lifted algorithm "produced significantly better solutions in general." Since the main argument is empirical, the comparison should be framed as a fixed-budget anytime comparison, with convergence statistics reported explicitly, and the claim of practical superiority should be restricted accordingly.
  4. [Section 6.5.1, Eq. (6.8); Section 2.3] The numerical robustness of the CCG and QUBO penalties is not addressed. The construction uses large weights such as L > w+1 for positive Boolean gadgets and J_ij > min(wi,wj) in the QUBO formulation of Eq. (6.8). If these parameters are chosen too small, constraints are violated; if too large, they can cause numerical accuracy problems in floating-point LP/ILP solvers and in the analog D-Wave hardware. Section 7.2.4 explicitly claims that the clique-based encoding has the advantage of avoiding "very large weights" and avoiding numerical accuracy issues, so the issue is recognized. The experiments should report the magnitudes of L and J_ij used, the precision settings of the solvers, and ideally a sensitivity analysis with respect to these penalty parameters.
minor comments (4)
  1. [Section 7.2.2] The bit ordering in the binary number-based encoding is not defined. The example says d=6 and Y=3 corresponds to XY,1=1, XY,2=1, XY,3=0, which is only correct if XY,1 is the least significant bit; this convention should be stated explicitly.
  2. [Section 2.2] There is a typo in the definition of constraints: "varibles" should be "variables." Similar typos appear in the Figure 5.1 captions, where "directed" should be "direct."
  3. [Section 5.2.3] In the CCG-based ILP encoding, the claim that each constraint has at most two variables should be qualified: the ILP formulation in Eq. (5.8) consists of edge constraints xi+xj≥1, so each such constraint has exactly two variables, while the objective function is unary over all vertices. This is fine, but the table entry "Number of Variables per Constraint ≤ 2" should be read as the width of the ILP constraints and would benefit from that clarification.
  4. [Section 6.6] The quantum annealing experiments use only two real-world Max-SAT instances and a set of 50 random instances with at most 50 variables. This is appropriate for a feasibility study, but the text should more prominently call these results preliminary, since the embedding step fails for the ILP-based HQCA and the CCG-based HQCA finds solutions far from optimal on the real-world instances.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the CCG-to-WCSP reduction is cited from prior peer-reviewed work, and the dissertation's contributions are independent applications with external benchmarks.

full rationale

The paper's derivation chain is not circular. The core CCG construction, including the flower+thorn gadget for positive nonlinear terms, is explicitly attributed to Kumar's prior work (Kumar 2008a; Kumar 2008b); the dissertation does not define WCSP optima in terms of CCG outputs and then claim to derive them. Instead, it takes the cited reduction as a premise and develops applications: the NT-reduction kernelization, lifted min-sum message passing, CCG-based ILP encoding, and CCG-based quantum annealing. The experimental chapters compare against external benchmark suites and independent solvers (toulbar2, Gurobi), and the main new theoretical claim, bipartiteness preservation of the CCG-based ILP encoding, is proved directly from the stated gadget structure. The sentence 'By constructing CCG gadgets that cancel out the lower order terms as shown before, we arrive at a lifted graphical representation of the positive nonlinear term' (Section 2.3) is an omitted proof and a genuine correctness risk for the positive nonlinear case, but it is a gap in a cited lemma, not a step that reduces to its own output by construction. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work. The self-citations to Kumar are normal reliance on an advisor's established framework and are not load-bearing in a circular sense, since the cited results are peer-reviewed and independent of this dissertation's specific claims. Therefore, the circularity score is low.

Assumptions & free parameters 5 free parameters · 5 assumptions · 2 invented entities

The dissertation's central claim rests on the unverified correctness of the CCG gadget construction (especially the positive-term cancellation with large weights L) and on several standard theorems cited from the optimization literature. The new non-Boolean encodings introduce additional free penalty weights and structural assumptions. These are not machine-checked and no code or data is provided to independently test them.

free parameters (5)
  • L (large penalty weight in CCG gadgets) = unspecified, must satisfy L > w + 1 for Boolean gadgets and L > w * prod(d_i - 1) for non-Boolean gadgets
    Introduced in Section 2.3 and Section 7.2.4 to cancel lower-order terms in the MWVC projection; its magnitude is a free choice that can affect numerical stability and solver performance.
  • J_ij (penalty coefficient in QUBO formulation of MWVC) = unspecified, must satisfy J_ij > min{w_i, w_j}
    Used in Section 6.5.1 to enforce vertex cover constraints in the D-Wave embedding; too large a value can cause precision errors, too small can break constraints.
  • alpha and beta (weights in ILP-based HQCA) = ratio alpha/beta > sum of all constraint weights, exact values not reported
    Governs the trade-off between constraint satisfaction and objective in the Ising formulation of Section 6.4; not systematically varied in experiments.
  • MSMP convergence threshold = 1e-6
    Used in Chapter 4.4 to declare convergence; different thresholds may change the reported convergence and solution quality results.
  • Small random weight perturbation = not quantified
    Added to weights in Chapter 3.2 to break ties in the maxflow-based NT reduction; the magnitude is unspecified and could affect kernelization outcomes.
assumptions (5)
  • domain assumption Correctness of the CCG construction, including the equivalence between WCSP and MWVC on the CCG
    The entire dissertation relies on this equivalence, cited from Kumar (2008a,b). It is not re-proved, formalized, or independently verified in this preprint.
  • standard math Half-integrality of the LP relaxation of MWVC (Nemhauser-Trotter)
    Cited in Chapter 3.1 as the basis for the NT reduction; a known theorem of linear programming.
  • standard math Total unimodularity of bipartite graph incidence matrices
    Used in Section 5.4 to argue that LP relaxation of MWVC on bipartite graphs has integer vertices; cited to Sierksma (2001).
  • domain assumption Maxflow solves MWVC on bipartite graphs in polynomial time
    Used in Chapter 3.1 for the NT reduction implementation; cited to Kumar (2003).
  • standard math Correctness of min-sum message passing on tree-structured factor graphs
    Background for Chapter 4; on loopy graphs the algorithm is a heuristic. The dissertation does not prove convergence or optimality for the CCG case.
invented entities (2)
  • Large-weight auxiliary 'thorn' vertices in CCG gadgets
    purpose: Enforce positive nonlinear terms by making it cheaper to select certain vertices in the MWVC, enabling the polynomial-to-graph reduction.
    These vertices are mathematical constructs introduced by the CCG construction. Their validity is supported only by the cited derivation, not by any independent falsifiable prediction.
  • Boolean variables introduced by the binary number-based, direct symmetric, and clique-based encodings for non-Boolean WCSP variables
    purpose: Represent multi-valued variables in the graph-based MWVC framework, extending the CCG beyond Boolean domains.
    These are representation devices new to this dissertation (Chapter 7). They have no empirical consequences beyond the mathematical equivalence they aim to establish, which is not independently tested.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exploiting Structure in the Boolean Weighted Constraint Satisfaction Problem: A Constraint Composite Graph-Based Approach." pith.science (2026). https://pith.science/paper/ITGOL3AI

@misc{pith2026260810005,
  author       = {Pith},
  title        = {Pith review of: Exploiting Structure in the Boolean Weighted Constraint Satisfaction Problem: A Constraint Composite Graph-Based Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ITGOL3AI}},
  note         = {Machine review of arXiv:2608.10005}
}
read the original abstract

What is "structure," and how can we exploit it in combinatorial optimization? Reasoning tasks such as system design, state estimation, and prediction can be cast as combinatorial optimization problems (COPs), traditionally attacked by dedicated algorithms that fail outside their narrow subclass, while communities working on equivalent problems reinvent each other's techniques. The weighted constraint satisfaction problem (WCSP) is a general framework that subsumes COPs from many communities and represents complex physical and non-physical systems, from spin glasses to social networks. Is such generality a curse? Our answer is to exploit "structure": a general-purpose WCSP algorithm should automatically imitate the specialized algorithm for whatever subclass its input belongs to. A WCSP has macro (graphical) structure, which variables interact, and micro (numerical) structure, how they interact. Separate schools of thought exploit one or the other, never both. The constraint composite graph (CCG), introduced in 2008, unifies them: it is an undirected graph over a WCSP instance's variables plus auxiliary ones, on which minimum weighted vertex cover (MWVC) solves the original instance. It is efficiently constructible, but largely unexploited. This dissertation answers three questions affirmatively. The CCG has theoretical advantages beyond identifying tractable classes (new properties proved here); it is practically useful (efficient implementation and experiments); and it extends promisingly to non-Boolean variables (new encodings). We use the CCG to (a) kernelize a WCSP instance, fixing optimal values of some variables by maxflow before search begins, (b) improve min-sum message passing, (c) exploit integer linear programming solvers, and (d) solve COPs on quantum annealers. Solving general COPs faster classically also yields better baselines for the debated quantum advantage.

Figures

Figures reproduced from arXiv: 2608.10005 by the authors.

Figure 1
Figure 1. ); in biophysics, it can be used to locate motifs in RNA sequences (Zyt [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 1.1
Figure 1.1. Illustrates the problem of finding the ground state energy of a random [PITH_FULL_IMAGE:figures/full_fig_p017_1_1.png] view at source ↗
Figure 1.2
Figure 1.2. Illustrates locating motifs in RNA sequences. Figure (a)a shows an [PITH_FULL_IMAGE:figures/full_fig_p018_1_2.png] view at source ↗
Figures from the paper (24 more)
Figure 2.1
Figure 2.1. Figure 2.1: Illustrates MWVCs. Each circle represents a vertex. The number [PITH_FULL_IMAGE:figures/full_fig_p025_2_1.png]
Figure 2.2
Figure 2.2. Figure 2.2: Shows an example binary constraint. The most mainstream class of algorithms for solving the WCSP is based on branch-and-bound search, which explores a search tree with each node representing an assignment of values to a subset of variables (Larrosa and Schiex 2004). …
Figure 2.3
Figure 2.3. Figure 2.3: Shows that the projection of MWVCs on the IS [PITH_FULL_IMAGE:figures/full_fig_p028_2_3.png]
Figure 2.4
Figure 2.4. Figure 2.4: Shows the lifted graphical representations of (a) linear, (b) negative [PITH_FULL_IMAGE:figures/full_fig_p029_2_4.png]
Figure 2.5
Figure 2.5. Figure 2.5: Illustrates the construction of the CCG for a given WCSP instance. [PITH_FULL_IMAGE:figures/full_fig_p030_2_5.png]
Figure 2.5
Figure 2.5. Figure 2.5: Continued. representation of a constraint depends on the nature of the terms in the polynomial that describes the constraint. We distinguish three classes of terms: linear terms, negative nonlinear terms, and positive nonlinear terms. We can construct a lifted graphi…
Figure 3.1
Figure 3.1. Figure 3.1: Illustrates kernelization algorithms. After a polynomial-time proce [PITH_FULL_IMAGE:figures/full_fig_p035_3_1.png]
Figure 3.2
Figure 3.2. Figure 3.2: Illustrates the NT reduction. The left-upper panel shows the graph [PITH_FULL_IMAGE:figures/full_fig_p036_3_2.png]
Figure 3.3
Figure 3.3. Figure 3.3: Shows the effectiveness of the NT reduction. The x-axes show the [PITH_FULL_IMAGE:figures/full_fig_p037_3_3.png]
Figure 3
Figure 3. Figure 3: shows the effectiveness of the NT reduction on the benchmark [PITH_FULL_IMAGE:figures/full_fig_p039_3.png]
Figure 4.1
Figure 4.1. Figure 4.1: Illustrates the factor graph of a Boolean WCSP instance with 3 [PITH_FULL_IMAGE:figures/full_fig_p043_4_1.png]
Figure 4.2
Figure 4.2. Figure 4.2: Shows the qualities of the solutions (total weights) produced by the [PITH_FULL_IMAGE:figures/full_fig_p050_4_2.png]
Figure 4.3
Figure 4.3. Figure 4.3: Shows the qualities of the solutions produced by the original MSMP [PITH_FULL_IMAGE:figures/full_fig_p051_4_3.png]
Figure 4
Figure 4. Figure 4: shows the qualities of the solutions (total weights) produced by [PITH_FULL_IMAGE:figures/full_fig_p053_4.png]
Figure 5
Figure 5. Figure 5: reports the comparison of efficiencies of the directed, improved [PITH_FULL_IMAGE:figures/full_fig_p068_5.png]
Figure 5.1
Figure 5.1. Figure 5.1: Compares the efficiencies of the direct, improved direct, and CCG [PITH_FULL_IMAGE:figures/full_fig_p069_5_1.png]
Figure 6.1
Figure 6.1. Figure 6.1: Shows the polynomial form of the binary constraint [PITH_FULL_IMAGE:figures/full_fig_p077_6_1.png]
Figure 6.2
Figure 6.2. Figure 6.2: Shows the Chimera graph in a D-Wave 2X processor. The Chimera [PITH_FULL_IMAGE:figures/full_fig_p081_6_2.png]
Figure 6.3
Figure 6.3. Figure 6.3: Compares suboptimalities of solutions produced by HQCAs on the two [PITH_FULL_IMAGE:figures/full_fig_p082_6_3.png]
Figure 6
Figure 6. Figure 6: compares the qualities of solutions produced by the polynomial [PITH_FULL_IMAGE:figures/full_fig_p084_6.png]
Figure 7.1
Figure 7.1. Figure 7.1: Shows the polynomial form of the constraint [PITH_FULL_IMAGE:figures/full_fig_p087_7_1.png]
Figure 7.2
Figure 7.2. Figure 7.2: Illustrates the high-degree polynomial-based encoding. In (b) and [PITH_FULL_IMAGE:figures/full_fig_p088_7_2.png]
Figure 7.3
Figure 7.3. Figure 7.3: Compares suboptimalities of solutions produced by the CCG-based [PITH_FULL_IMAGE:figures/full_fig_p096_7_3.png]
Figure 7
Figure 7. Figure 7: compares the qualities of solutions produced by the CCG-based [PITH_FULL_IMAGE:figures/full_fig_p097_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

4 extracted references · 2 canonical work pages

  1. [146]

    Solving Large Scale Max Cut Problems via Tabu Search

    doi: 10.1145/956750.956769. Kochenberger, Gary A., Jin-Kao Hao, Zhipeng L¨ u, Haibo Wang, and Fred Glover (2013). “Solving Large Scale Max Cut Problems via Tabu Search”. In: Journal of Heuristics 19.4, pp. 565–571. doi: 10.1007/s10732-011-9189-8 . Koller, Daphne and Nir Friedman (2009). Probabilistic Graphical Models: Princi- ples and Techniques. MIT Pres...

    arXiv 2013

  2. [209]

    Max-sum Revisited; The Real Power of Damp- ing

    doi: 10.1007/s11128-008-0082-9 . Cohen, Liel and Roie Zivan (2017). “Max-sum Revisited; The Real Power of Damp- ing”. In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems , pp. 1505–1507. Cohen, Liel and Roie Zivan (2018). “Balancing Asymmetry in Max-sum Using Split Constraint Factor Graphs”. In: Proceedings of the I...

    doi:10.1007/s11128-008-0082-9 2017

  3. [496]

    Constraint Networks

    doi: 10.1007/BF02178370. Dechter, Rina (1992). “Constraint Networks”. In: Encyclopedia of Artificial Intel- ligence, pp. 276–285. D-Wave Systems Inc. (2017). Developer Guide for Python (09-1024A-F) . 106 Easley, David and Jon Kleinberg (2010). Networks, Crowds, and Markets: Rea- soning About a Highly Connected World . Cambridge University Press. isbn: 978-...

    work page doi:10.1007/bf02178370 1992

  4. [1178]

    Power-law Citation Distributions are not Scale-Free

    url: http : / / www . sciencedirect . com / science / article / pii / S1002007108002219. Golosovsky, Michael (2017). “Power-law Citation Distributions are not Scale-Free”. In: Physical Review E 96.3, p. 032306. doi: 10.1103/PhysRevE.96.032306. Grauer-Gray, Scott, Chandra Kambhamettu, and Kannappan Palaniappan (2008). “GPU Implementation of Belief Propagat...

    work page arXiv 2017

Pith tools

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