The subgraph sampling scheme (SSS) is a technique originally introduced for Markov random fields. It is a powerful tool for designing heuristic algorithms for max-cut, quadratic unconstrained binary optimization (QUBO), and other optimization problems. The first application of SSS in combinatorial optimization, combined with dynamic programming, is in Selby’s heuristic. This algorithm is shown to outperform quantum annealing for solving max-cut problems on chimera graphs. Leveraging SSS, we introduce two new algorithms. One is designed to handle general graphs, whereas the other is specifically tailored for toroidal grid graphs. To assess the effectiveness of these algorithms, we conducted a comprehensive evaluation. We used the same methodology, test bed, and set of 37 well-established heuristics for max-cut and QUBO problems as described in a recent study of Dunning, Gupta, and Silberholz. Notably, all three SSS-based algorithms consistently achieve top rankings in terms of performance. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the funding program Horizon 2020 - Excellent Science - Marie Skłodowska-Curie Actions of the European Commission (Grant MINOA- Mixed-Integer Non-Linear Optimization Applications/764759]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0812 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0812 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

A present trend in the study of the symmetric traveling salesman polytope is to use, as a relaxation of the polytope, the graphical traveling salesman polyhedron (GTSP). Following a parallel approach for the asymmetric traveling salesman polytope, we define the graphical asymmetric traveling salesman problem on a general digraph D and its associated polyhedron GATSP(D). We give basic polyhedral results and lifting theorems for GATSP(D) and we give a general condition for a facet-defining inequality for GTSP to yield a symmetric facet-defining inequality for GATSP. Using this approach we show that all known major families of facet-defining inequalities of GTSP define facets of GATSP. Finally, we discuss possible extension of these results to the asymmetric traveling salesman polytope.