pith. sign in

arxiv: 2502.03669 · v3 · submitted 2025-02-05 · 💻 cs.LG · cs.AI· cs.DM· math.OC· stat.ML

Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set

Yikai Wu , Haoyu Zhao , Sanjeev Arora This is my paper

Pith reviewed 2026-05-23 03:36 UTC · model grok-4.3

classification 💻 cs.LG cs.AIcs.DMmath.OCstat.ML
keywords maximum independent setcombinatorial optimizationAI methodsclassical algorithmsGFlowNetsKaMISserialization analysisrandom graphs
0
0 comments X

The pith

Leading AI methods for maximum independent set are consistently outperformed by a classical solver on a single CPU even on random graphs.

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

The paper directly compares GPU-based AI approaches, including generative models and reinforcement learning, to classical CPU algorithms on the maximum independent set problem. It reports that these AI methods produce smaller independent sets than the classical solver KaMIS on random graphs that match the training distribution, and that some AI methods do not even exceed a basic degree-based greedy heuristic. A new serialization technique shows that non-backtracking AI methods arrive at decisions that closely resemble the greedy heuristic rather than exploiting more global structure. The same experiments indicate that KaMIS scales effectively to graphs with a million nodes, which bears on an earlier conjecture about the size of maximum independent sets in sparse random graphs. The findings lead the authors to call for tighter benchmarking and greater use of classical heuristics inside AI pipelines for combinatorial optimization.

Core claim

Even on in-distribution random graphs, leading AI-inspired methods are consistently outperformed by the state-of-the-art classical solver KaMIS running on a single CPU, and some AI-inspired methods frequently fail to surpass even the simplest degree-based greedy heuristic. Even with post-processing techniques like local search, AI-inspired methods still perform worse than CPU-based solvers. Serialization analysis reveals that non-backtracking AI-inspired methods, such as LTFT based on GFlowNets, end up reasoning similarly to the degree-based greedy heuristic and thus worse than KaMIS. KaMIS exhibits strong performance on sparse random graphs up to 10^6 nodes, suggesting that the shattering阈值

What carries the argument

Serialization analysis that converts the sequential decisions of non-backtracking AI methods into an explicit ordering to expose their similarity to classical greedy selection.

If this is right

  • Current AI approaches to combinatorial optimization require rethinking to incorporate classical techniques.
  • More rigorous benchmarking against established solvers is needed before claiming superiority for AI methods.
  • Principled integration of classical heuristics can improve AI performance on NP-hard problems.
  • KaMIS performance on large sparse graphs indicates that the shattering threshold conjecture does not hold at practical sizes around 10^6 nodes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The performance gap may extend to other NP-hard problems where similar non-backtracking AI architectures are applied.
  • Hybrid methods that add explicit backtracking to GFlowNet-style models could be tested to determine whether the serialization limitation can be overcome.
  • The strong scaling of KaMIS on million-node instances suggests classical solvers may remain competitive on distributions previously thought difficult for exact methods.
  • Re-evaluating AI training objectives to reward global optimality rather than local greedy-like choices might narrow the gap on in-distribution instances.

Load-bearing premise

The tested AI methods and training regimes are representative of current best practices, so the observed performance gaps are not caused by implementation details or unequal compute budgets.

What would settle it

Running the same AI methods with additional training epochs, different hyperparameters, or equivalent total compute on the identical random-graph test set and obtaining independent sets larger than those returned by KaMIS would falsify the central performance claim.

Figures

Figures reproduced from arXiv: 2502.03669 by Haoyu Zhao, Sanjeev Arora, Yikai Wu.

Figure 1
Figure 1. Figure 1: Analysis on ER graphs in (a) Section 5.1 and (b) Section 5.2 5.2 Serialization: allows comparing to Deg-Greedy In the previous part, we demonstrate that LTFT employs a heuristic similar to Deg-Greedy, selecting the node with the smallest degree in the remaining graph in each round. However, other algorithms, such as ReduMIS, PCQO, and DIFUSCO, which does not select one node at a step without backtracking, … view at source ↗
Figure 2
Figure 2. Figure 2: Percentage of rounds when LTFT selects the node with smallest possible degree on BA graphs. On BA graphs, the percentage to choose the smallest possible node is generally lower, but on denser BA graphs LTFT also behaves more like degree-based greedy. These results reinforced our observations in Section 5.2. First, the percentage for Deg-Greedy and LTFT are generally high. Deg-Greedy reaches 100% for all pa… view at source ↗
Figure 3
Figure 3. Figure 3: The percentage to choose the smallest possible degree node on different part of the serialization for all ER graphs It reinforces our observations in Section 5.2. In addition, we also observe that algorithms similar to Deg-Greedy (Deg-Greedy and LTFT) and good-performing algorithms (OnlineMIS, ReduMIS, iSCO, and LwD) have clearly different characteristics across various (n, d), described in Appendix C.4. 2… view at source ↗
Figure 4
Figure 4. Figure 4: The percentage to choose the smallest possible degree node on different part of the serialization for all BA graphs It reinforces our observations in Section 5.2. In addition, we also observe that algorithms similar to Deg-Greedy (Deg-Greedy and LTFT) and good-performing algorithms (OnlineMIS, ReduMIS, iSCO, and LwD) have clearly different characteristics across various (n, m), described in Appendix C.4. 2… view at source ↗
Figure 5
Figure 5. Figure 5: Percentage of the smallest possible degree node in the pseudo-natural serialization of LwD, i.e., behaves similarly to degree-based greedy, for the 3 equal parts of the serialization, and the overal average From the overall heatmaps, we can see LwD is not very similar to Deg-Greedy like LTFT. From the heatmaps for different 1/3 parts, we can see the percentage increases from the 1st 1/3 to the 3rd 1/3 for … view at source ↗
Figure 6
Figure 6. Figure 6: Heatmap for ratios of MIS size to nln(d)/d on ER graphs with number of nodes n and average degree d. We can see that ReduMIS, OnlineMIS, and iSCO has consitently high ratios more than 1.2. Ran-Greedy stays around 1.0 for all (n, d). Other algorithms, including Deg-Greedy, all have higher ratios for sparser graphs, but lower ratios (close to 1) for denser graphs. 28 [PITH_FULL_IMAGE:figures/full_fig_p028_6.png] view at source ↗
read the original abstract

AI methods, such as generative models and reinforcement learning, have recently been applied to combinatorial optimization (CO) problems, especially NP-hard ones. This paper compares such GPU-based methods with classical CPU-based methods on the Maximum Independent Set (MIS) problem. Strikingly, even on in-distribution random graphs, leading AI-inspired methods are consistently outperformed by the state-of-the-art classical solver KaMIS running on a single CPU, and some AI-inspired methods frequently fail to surpass even the simplest degree-based greedy heuristic. Even with post-processing techniques like local search, AI-inspired methods still perform worse than CPU-based solvers. To better understand the source of these failures, we introduce a novel analysis, serialization, which reveals that non-backtracking AI-inspired methods, e.g. LTFT (which is based on GFlowNets), end up reasoning similarly to the simplest degree-based greedy, and thus worse than KaMIS. More generally, our findings suggest a need for a rethinking of current approaches in AI for CO, advocating for more rigorous benchmarking and the principled integration of classical heuristics. Additionally, we also find that CPU-based algorithm KaMIS have strong performance on sparse random graphs, which appears to show that the shattering threshold conjecture for large independent sets proposed by Coja-Oghlan & Efthymiou (2015) does not apply for real-life sizes (such as 10^6 nodes).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper empirically compares GPU-based AI methods (including generative models, RL, and GFlowNet-based LTFT) for the Maximum Independent Set problem against classical CPU-based solvers such as KaMIS on random graphs. It claims that even on in-distribution instances, KaMIS consistently outperforms the AI methods, some of which fail to beat simple degree-greedy heuristics; post-processing like local search does not close the gap. The authors introduce a 'serialization' diagnostic showing that non-backtracking AI methods behave similarly to greedy algorithms. They also report that KaMIS performs strongly on large sparse random graphs, suggesting the shattering threshold conjecture does not hold at practical scales (~10^6 nodes).

Significance. If the central empirical results prove robust, the work would be significant for the AI-for-CO community by documenting concrete performance gaps against strong classical baselines and by providing the serialization diagnostic as a tool for analyzing solver behavior. The call for more rigorous benchmarking and hybrid approaches is timely. The observation regarding the shattering threshold on real-life graph sizes could stimulate follow-up theoretical and empirical work if the experimental conditions are fully specified.

major comments (3)
  1. [Experimental methods / §4] Experimental methods section: the manuscript states clear performance claims (e.g., KaMIS outperforming AI methods on in-distribution random graphs) but supplies no details on graph-generation parameters (n, p), number of independent trials, error bars, statistical tests, or training hyperparameters/compute budgets for the AI pipelines (including LTFT). These omissions are load-bearing for assessing whether the reported gaps are representative or artifacts of implementation.
  2. [Results / Discussion] Resource comparison: the headline claim that single-CPU KaMIS outperforms GPU-trained AI methods is not accompanied by wall-clock or FLOPs-matched controls, even though the text acknowledges the disparity. Without such quantification, it is impossible to determine whether the performance ordering would persist under equivalent resource allocation.
  3. [Serialization analysis subsection] Serialization diagnostic: the new analysis is presented as revealing that non-backtracking AI methods (e.g., LTFT) reason like degree-greedy, yet the manuscript does not report validation of the diagnostic on controlled synthetic cases or demonstrate that it distinguishes implementation artifacts from fundamental architectural limits.
minor comments (2)
  1. [Abstract] Abstract: the phrase 'some AI-inspired methods frequently fail to surpass even the simplest degree-based greedy heuristic' should be accompanied by at least one concrete quantitative example or table reference.
  2. [Introduction / Methods] Notation: ensure consistent use of 'serialization' versus any related terms when first introduced.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive feedback, which highlights important aspects of experimental rigor and analysis. We address each major comment below and will revise the manuscript to incorporate additional details and clarifications where needed.

read point-by-point responses

  1. Referee: [Experimental methods / §4] Experimental methods section: the manuscript states clear performance claims (e.g., KaMIS outperforming AI methods on in-distribution random graphs) but supplies no details on graph-generation parameters (n, p), number of independent trials, error bars, statistical tests, or training hyperparameters/compute budgets for the AI pipelines (including LTFT). These omissions are load-bearing for assessing whether the reported gaps are representative or artifacts of implementation.

    Authors: We agree these details are necessary for reproducibility and evaluating result robustness. The revised manuscript will specify the graph generation parameters (n and p values for Erdős–Rényi graphs), number of independent trials, inclusion of error bars, any statistical tests performed, and full training hyperparameters plus compute budgets for all AI methods including LTFT. This addresses the concern directly without altering the core claims. revision: yes

  2. Referee: [Results / Discussion] Resource comparison: the headline claim that single-CPU KaMIS outperforms GPU-trained AI methods is not accompanied by wall-clock or FLOPs-matched controls, even though the text acknowledges the disparity. Without such quantification, it is impossible to determine whether the performance ordering would persist under equivalent resource allocation.

    Authors: The manuscript acknowledges the CPU/GPU disparity but does not provide matched controls. We will add wall-clock timings for inference (and training where relevant) and approximate FLOPs estimates for the AI pipelines versus KaMIS runtime on the same hardware class. This will allow assessment of whether the ordering holds under more comparable resource budgets, while noting that training costs for AI methods are an inherent part of their practical deployment. revision: yes

  3. Referee: [Serialization analysis subsection] Serialization diagnostic: the new analysis is presented as revealing that non-backtracking AI methods (e.g., LTFT) reason like degree-greedy, yet the manuscript does not report validation of the diagnostic on controlled synthetic cases or demonstrate that it distinguishes implementation artifacts from fundamental architectural limits.

    Authors: The serialization analysis is presented as a diagnostic tool based on observed behavior on the evaluated instances. To strengthen it, the revision will include validation experiments on controlled synthetic cases (e.g., graphs where greedy behavior is known a priori) to show that the diagnostic can differentiate reasoning patterns and is not limited to implementation artifacts. This will clarify its scope as a behavioral probe. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical benchmark with independent diagnostic

full rationale

This is an empirical comparison paper with no derivation chain, equations, or first-principles predictions. The central claims rest on benchmark results (KaMIS vs. AI methods on random graphs) and a new analysis tool called serialization whose definition and application are described independently of the performance numbers. No fitted parameters are renamed as predictions, no self-citations bear load on uniqueness theorems, and no ansatz is smuggled in. The work is self-contained against external benchmarks (KaMIS, greedy heuristics) and does not reduce any result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, no free parameters, ad-hoc axioms, or invented entities are introduced; the work relies on standard assumptions about random graph models and solver fairness.

axioms (1)
  • domain assumption The random graphs tested are in-distribution for the trained AI methods
    Explicitly referenced in the abstract when stating performance 'even on in-distribution random graphs'.

pith-pipeline@v0.9.0 · 5796 in / 1320 out tokens · 37191 ms · 2026-05-23T03:36:00.941408+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Mutation-Guided Differentiable Quadratic Combinatorial Optimization

    cs.DM 2026-05 unverdicted novelty 5.0

    mQO combines differentiable QUBO optimization with mutation-based resets and local search to outperform heuristics and solvers on large-scale combinatorial problems by addressing stalling in local maxima.

Reference graph

Works this paper leans on

86 extracted references · 86 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Handbook of combinatorial optimization , volume 4

    Dingzhu Du and Panos M Pardalos. Handbook of combinatorial optimization , volume 4. Springer Science & Business Media, 1998

    work page 1998

  2. [2]

    Combinatorial optimization: Current successes and directions for the future

    Karla L Hoffman. Combinatorial optimization: Current successes and directions for the future. Journal of computational and applied mathematics, 124(1-2):341–360, 2000

    work page 2000

  3. [3]

    Preface: Combinatorial optimization drives the future of health care

    Liwei Zhong and Guochun Tang. Preface: Combinatorial optimization drives the future of health care. Journal of Combinatorial Optimization, 42:675–676, 2021

    work page 2021

  4. [4]

    Combinatorial optimization: algorithms and complexity

    Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998

    work page 1998

  5. [5]

    Gurobi Optimizer Reference Manual, 2024

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024

    work page 2024

  6. [6]

    Combinatorial optimization with graph convolu- tional networks and guided tree search

    Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. Advances in neural information processing systems, 31, 2018

    work page 2018

  7. [7]

    Learning what to defer for maximum in- dependent sets

    Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum in- dependent sets. In International conference on machine learning , pages 134–144. PMLR, 2020

    work page 2020

  8. [8]

    Attention, Learn to Solve Routing Problems!

    Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  9. [9]

    Solving dynamic traveling salesman problems with deep reinforcement learning

    Zizhen Zhang, Hong Liu, MengChu Zhou, and Jiahai Wang. Solving dynamic traveling salesman problems with deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 34(4):2119–2132, 2021

    work page 2021

  10. [10]

    Machine learning for combinatorial optimization: a methodological tour d’horizon

    Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021

    work page 2021

  11. [11]

    Combinatorial optimization and reasoning with graph neural networks

    Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veliˇckovi´c. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1–61, 2023

    work page 2023

  12. [12]

    Learning combinatorial optimization algorithms over graphs

    Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017

    work page 2017

  13. [13]

    Learning to branch

    Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International conference on machine learning, pages 344–353. PMLR, 2018

    work page 2018

  14. [14]

    Solving mixed integer programs using neural networks

    Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid V on Glehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020

    work page arXiv 2012

  15. [15]

    Difusco: Graph-based diffusion solvers for combinatorial optimization

    Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in Neural Information Processing Systems, 36:3706–3731, 2023. 10

    work page 2023

  16. [16]

    A diffusion model framework for unsupervised neural combinatorial optimization

    Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. A diffusion model framework for unsupervised neural combinatorial optimization. In Forty-first International Conference on Machine Learning, 2024

    work page 2024

  17. [17]

    Revisiting sampling for combinatorial optimization

    Haoran Sun, Katayoon Goshvadi, Azade Nova, Dale Schuurmans, and Hanjun Dai. Revisiting sampling for combinatorial optimization. In International Conference on Machine Learning, pages 32859–32874. PMLR, 2023

    work page 2023

  18. [18]

    Dataless quadratic neural networks for the maximum independent set problem

    Ismail Alkhouri, Cedric Le Denmat, Yingjie Li, Cunxi Yu, Jia Liu, Rongrong Wang, and Alvaro Velasquez. Dataless quadratic neural networks for the maximum independent set problem. arXiv preprint arXiv:2406.19532, 2024

    work page arXiv 2024

  19. [19]

    Flow network based generative models for non-iterative diverse candidate generation

    Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 34:27381–27394, 2021

    work page 2021

  20. [20]

    Gflownet foundations

    Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J Hu, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations. The Journal of Machine Learning Research, 24(1):10006–10060, 2023

    work page 2023

  21. [21]

    Let the flows tell: Solving graph combinatorial problems with gflownets

    Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in neural information processing systems, 36:11952–11969, 2023

    work page 2023

  22. [22]

    Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set

    Maria Chiara Angelini and Federico Ricci-Tersenghi. Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set. Nature Machine Intelligence, 5(1):29–31, 2023

    work page 2023

  23. [23]

    Combinatorial optimization with physics-inspired graph neural networks

    Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367–377, 2022

    work page 2022

  24. [24]

    What’s wrong with deep learning in tree search for combinatorial optimization

    Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What’s wrong with deep learning in tree search for combinatorial optimization. In Proceedings of the International Conference on Learning Representations (ICLR), 2022

    work page 2022

  25. [25]

    Barriers for the performance of graph neural networks (gnn) in discrete random structures

    David Gamarnik. Barriers for the performance of graph neural networks (gnn) in discrete random structures. Proceedings of the National Academy of Sciences, 120(46):e2314092120, 2023

    work page 2023

  26. [26]

    Learning the travelling salesperson problem requires rethinking generalization

    Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, 27(1):70–98, 2022

    work page 2022

  27. [27]

    Position: Rethinking post-hoc search-based neural approaches for solving large-scale traveling salesman problems

    Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post-hoc search-based neural approaches for solving large-scale traveling salesman problems. In International Conference on Machine Learning , pages 54178–54190. PMLR, 2024

    work page 2024

  28. [28]

    Finding near-optimal independent sets at scale

    Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato Werneck. Finding near-optimal independent sets at scale. Journal of Heuristics, 23(4), 2017

    work page 2017

  29. [29]

    Scalable kernelization for maximum independent sets

    Demian Hespe, Christian Schulz, and Darren Strash. Scalable kernelization for maximum independent sets. Journal of Experimental Algorithmics (JEA), 24:1–22, 2019

    work page 2019

  30. [30]

    Finding maximum independent sets in graphs arising from coding theory

    Sergiy Butenko, Panos Pardalos, Ivan Sergienko, Vladimir Shylo, and Petro Stetsyuk. Finding maximum independent sets in graphs arising from coding theory. In Proceedings of the 2002 ACM symposium on Applied computing, pages 542–546, 2002

    work page 2002

  31. [31]

    Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs

    Mingyu Xiao and Hiroshi Nagamochi. Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs. Theoretical Computer Science, 469:92–104, 2013

    work page 2013

  32. [32]

    Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover

    Takuya Akiba and Yoichi Iwata. Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover. Theoretical Computer Science, 609:211–225, 2016. 11

    work page 2016

  33. [33]

    Fast local search for the maximum independent set problem

    Diogo V Andrade, Mauricio GC Resende, and Renato F Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18:525–547, 2012

    work page 2012

  34. [34]

    An evolutionary heuristic for the maximum independent set problem

    Thomas Back and Sami Khuri. An evolutionary heuristic for the maximum independent set problem. In Proceedings of the first IEEE conference on evolutionary computation. IEEE World Congress on Computational Intelligence, pages 531–535. IEEE, 1994

    work page 1994

  35. [35]

    Experimental comparison of two evolutionary algorithms for the independent set problem

    Pavel A Borisovsky and Marina S Zavolovskaya. Experimental comparison of two evolutionary algorithms for the independent set problem. In Workshops on Applications of Evolutionary Computation, pages 154–164. Springer, 2003

    work page 2003

  36. [36]

    Graph partitioning for independent sets

    Sebastian Lamm, Peter Sanders, and Christian Schulz. Graph partitioning for independent sets. In International Symposium on Experimental Algorithms, pages 68–81. Springer, 2015

    work page 2015

  37. [37]

    Accelerating local search for the maximum independent set problem

    Jakob Dahlum, Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Accelerating local search for the maximum independent set problem. In Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings 15, pages 118–133. Springer, 2016

    work page 2016

  38. [38]

    Vertex packings: structural properties and algorithms

    George L Nemhauser and Leslie E Trotter Jr. Vertex packings: structural properties and algorithms. Mathematical Programming, 8(1):232–248, 1975

    work page 1975

  39. [39]

    From distribution learning in training to gradient search in testing for combinatorial optimization

    Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

  40. [40]

    Dimes: A differentiable meta solver for combinatorial optimization problems

    Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35:25531–25546, 2022

    work page 2022

  41. [41]

    Varia- tional annealing on graphs for combinatorial optimization

    Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, and Sebastian Lehner. Varia- tional annealing on graphs for combinatorial optimization. Advances in Neural Information Processing Systems, 36:63907–63930, 2023

    work page 2023

  42. [42]

    Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs

    Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33:6659–6672, 2020

    work page 2020

  43. [43]

    Annealed training for combinatorial optimiza- tion on graphs

    Haoran Sun, Etash Kumar Guha, and Hanjun Dai. Annealed training for combinatorial optimiza- tion on graphs. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022

    work page 2022

  44. [44]

    Controlling continuous relaxation for combinatorial optimization

    Yuma Ichikawa. Controlling continuous relaxation for combinatorial optimization. arXiv preprint arXiv:2309.16965, 2023

    work page arXiv 2023

  45. [45]

    Erdös and A

    P. Erdös and A. Rényi. On random graphs i. Publicationes Mathematicae Debrecen, 6:290, 1959

    work page 1959

  46. [46]

    Statistical mechanics of complex networks

    Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002

    work page 2002

  47. [47]

    Exact phase transitions in random constraint satisfaction problems

    Ke Xu and Wei Li. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 12:93–103, 2000

    work page 2000

  48. [48]

    Deep graph kernels

    Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365–1374, 2015

    work page 2015

  49. [49]

    Limits of local algorithms over sparse random graphs

    David Gamarnik and Madhu Sudan. Limits of local algorithms over sparse random graphs. In Proceedings of the 5th conference on Innovations in theoretical computer science , pages 369–376, 2014

    work page 2014

  50. [50]

    The overlap gap property: A topological barrier to optimizing over random structures

    David Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures. Proceedings of the National Academy of Sciences, 118(41):e2108492118, 2021. 12

    work page 2021

  51. [51]

    On independent sets in random graphs

    Amin Coja-Oghlan and Charilaos Efthymiou. On independent sets in random graphs. Random Structures & Algorithms, 47(3):436–486, 2015

    work page 2015

  52. [52]

    On colouring random graphs

    Geoffrey R Grimmett and Colin JH McDiarmid. On colouring random graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 77, pages 313–324. Cambridge University Press, 1975

    work page 1975

  53. [53]

    Local algorithms for independent sets are half-optimal

    Mustazee Rahman and Bálint Virág. Local algorithms for independent sets are half-optimal. Annals of Probability, 45(3), 2017

    work page 2017

  54. [54]

    The hard-core model on random graphs revisited

    Jean Barbier, Florent Krzakala, Lenka Zdeborová, and Pan Zhang. The hard-core model on random graphs revisited. In Journal of Physics: Conference Series, volume 473, page 012021. IOP Publishing, 2013

    work page 2013

  55. [55]

    Maximum independent sets on random regular graphs

    Jian Ding, Allan Sly, and Nike Sun. Maximum independent sets on random regular graphs. Acta Mathematica, 217(2):263–340, 2016

    work page 2016

  56. [56]

    Analysis of greedy algorithms on graphs with bounded degrees

    Nicholas C Wormald. Analysis of greedy algorithms on graphs with bounded degrees. Discrete Mathematics, 273(1-3):235–260, 2003

    work page 2003

  57. [57]

    Approximating maximum independent sets by excluding subgraphs

    Ravi Boppana and Magnús M Halldórsson. Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2):180–196, 1992

    work page 1992

  58. [58]

    The traveling salesman problem: An overview of exact and approximate algorithms

    Gilbert Laporte. The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2):231–247, 1992

    work page 1992

  59. [59]

    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

    work page 1995

  60. [60]

    Fast algorithms for max independent set

    Nicolas Bourgeois, Bruno Escoffier, Vangelis T Paschos, and Johan MM van Rooij. Fast algorithms for max independent set. Algorithmica, 62:382–415, 2012

    work page 2012

  61. [61]

    Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs

    Eran Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM Journal on Computing, 31(5):1608–1623, 2002

    work page 2002

  62. [62]

    Approximating independent sets in sparse graphs

    Nikhil Bansal. Approximating independent sets in sparse graphs. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1–8. SIAM, 2014

    work page 2014

  63. [63]

    Learning to perform local rewriting for combinatorial optimization

    Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in neural information processing systems, 32, 2019

    work page 2019

  64. [64]

    Reinforcement learning with combinatorial actions: An application to vehicle routing

    Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with combinatorial actions: An application to vehicle routing. Advances in Neural Information Processing Systems, 33:609–620, 2020

    work page 2020

  65. [65]

    Deep reinforcement learning for combinatorial optimization: Covering salesman problems

    Kaiwen Li, Tao Zhang, Rui Wang, Yuheng Wang, Yi Han, and Ling Wang. Deep reinforcement learning for combinatorial optimization: Covering salesman problems. IEEE transactions on cybernetics, 52(12):13142–13155, 2021

    work page 2021

  66. [66]

    Combining reinforcement learning with lin-kernighan-helsgaun algorithm for the traveling salesman problem

    Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. Combining reinforcement learning with lin-kernighan-helsgaun algorithm for the traveling salesman problem. In Pro- ceedings of the AAAI conference on artificial intelligence , volume 35, pages 12445–12452, 2021

    work page 2021

  67. [67]

    Deepaco: neural-enhanced ant systems for combinatorial optimization.Advances in Neural Information Processing Systems, 36, 2024

    Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. Deepaco: neural-enhanced ant systems for combinatorial optimization.Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

  68. [68]

    Smart manufacturing scheduling with edge computing using multiclass deep q network

    Chun-Cheng Lin, Der-Jiunn Deng, Yen-Ling Chih, and Hsin-Ting Chiu. Smart manufacturing scheduling with edge computing using multiclass deep q network. IEEE Transactions on Industrial Informatics, 15(7):4276–4284, 2019. 13

    work page 2019

  69. [69]

    Multi-agent reinforcement learning for job shop scheduling in flexible manufacturing systems

    Schirin Baer, Jupiter Bakakeu, Richard Meyes, and Tobias Meisen. Multi-agent reinforcement learning for job shop scheduling in flexible manufacturing systems. In2019 Second International Conference on Artificial Intelligence for Industries (AI4I), pages 22–25. IEEE, 2019

    work page 2019

  70. [70]

    Learning to dispatch for job shop scheduling via deep reinforcement learning

    Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances in neural information processing systems, 33:1621–1632, 2020

    work page 2020

  71. [71]

    Learning to solve circuit-sat: An unsupervised differentiable approach

    Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An unsupervised differentiable approach. In International Conference on Learning Representations, 2019

    work page 2019

  72. [72]

    G2sat: Learning to generate sat formulas

    Jiaxuan You, Haoze Wu, Clark Barrett, Raghuram Ramanujan, and Jure Leskovec. G2sat: Learning to generate sat formulas. Advances in neural information processing systems , 32, 2019

    work page 2019

  73. [73]

    Can q-learning with graph networks learn a generalizable branching heuristic for a sat solver? Advances in Neural Information Processing Systems, 33:9608–9621, 2020

    Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. Can q-learning with graph networks learn a generalizable branching heuristic for a sat solver? Advances in Neural Information Processing Systems, 33:9608–9621, 2020

    work page 2020

  74. [74]

    Nsnet: A general neural probabilistic framework for satisfiability problems

    Zhaoyu Li and Xujie Si. Nsnet: A general neural probabilistic framework for satisfiability problems. Advances in Neural Information Processing Systems, 35:25573–25585, 2022

    work page 2022

  75. [75]

    Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong structure-hardness-aware baseline

    Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong structure-hardness-aware baseline. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4414–4425, 2023

    work page 2023

  76. [76]

    Dags with no tears: Continuous optimization for structure learning

    Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Continuous optimization for structure learning. Advances in neural information processing systems, 31, 2018

    work page 2018

  77. [77]

    Causal discovery with reinforcement learning

    Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal discovery with reinforcement learning. In International Conference on Learning Representations, 2020

    work page 2020

  78. [78]

    Diffusion models for causal discovery via topological ordering

    Pedro Sanchez, Xiao Liu, Alison Q O’Neil, and Sotirios A Tsaftaris. Diffusion models for causal discovery via topological ordering. arXiv preprint arXiv:2210.06201, 2022

    work page arXiv 2022

  79. [79]

    Network science: Theory and applications

    Ted G Lewis. Network science: Theory and applications. John Wiley & Sons, 2011

    work page 2011

  80. [80]

    Random graphs

    Béla Bollobás and Béla Bollobás. Random graphs. Springer, 1998

    work page 1998

Showing first 80 references.