Pith. sign in

REVIEW 13 cited by

An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1906.01227 v2 pith:I6HXFJMW submitted 2019-06-04 cs.LG stat.ML

Chaitanya K. Joshi , Thomas Laurent , Xavier Bresson This is my paper · ORCID
classification cs.LGstat.ML
keywords graphapproachproblemconvolutionaldeepefficientlearning-basednodes
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

This paper introduces a new learning-based approach for approximately solving the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph Convolutional Networks to build efficient TSP graph representations and output tours in a non-autoregressive manner via highly parallelized beam search. Our approach outperforms all recently proposed autoregressive deep learning techniques in terms of solution quality, inference speed and sample efficiency for problem instances of fixed graph sizes. In particular, we reduce the average optimality gap from 0.52% to 0.01% for 50 nodes, and from 2.26% to 1.39% for 100 nodes. Finally, despite improving upon other learning-based approaches for TSP, our approach falls short of standard Operations Research solvers.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 13 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. OpenAlex reports about 203 citations worldwide. Full citation record

  1. TSP with Predictions: Heatmap to Tour with Provable Guarantees

    cs.DS 2026-07 conditional novelty 8.0 of 10

    Any TSP heatmap of L1 error η yields a tour of cost ≤ OPT + 2η via a prediction-biased Christofides algorithm, with matching near-linear variants and experiments.

  2. LaT: LLM-as-Trainer for Multi-Task Vehicle Routing Solvers

    cs.AI 2026-07 conditional novelty 6.0 of 10

    A pretrained LLM converts cross-task validation gaps into a five-number guidance signal injected into each encoder layer, improving several multi-task VRP solvers by roughly 0.1–0.5 percentage points on trained and un...

  3. GeoRouteNet: A Geometry-Aware Non-Autoregressive Neural Solver for the Euclidean Traveling Salesman Problem

    cs.LG 2026-06 unverdicted novelty 6.0 of 10

    GeoRouteNet improves non-autoregressive neural TSP solvers via geometric inductive biases and MCS-RL training, reporting 0.32% gap on TSP50, 1.26% on TSP100, and 3.60% on TSPLIB instances with higher throughput than C...

  4. Recurrent State Encoders for Efficient Neural Combinatorial Optimization

    cs.LG 2025-09 conditional novelty 6.0 of 10

    A recurrent encoder that updates embeddings from prior step embeddings and current state matches a 9-layer recompute-every-step encoder with 3x fewer active layers, cutting latency 1.8-4x on TSP, CVRP, and OP.

  5. SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy

    cs.AI 2025-06 conditional novelty 6.0 of 10

    SHIELD combines Mixture-of-Depths sparsity and context-aware clustering to outperform prior unified neural solvers on multi-task, multi-distribution vehicle routing.

  6. Hierarchical Learning-based Graph Partition for Large-scale Vehicle Routing Problems

    cs.LG 2025-02 conditional novelty 6.0 of 10

    A hierarchical graph-partition framework with K local two-way re-partition levels improves neural CVRP solvers at scales up to 10,000 customers.

  7. MDGAM-Based Cooperative Task Scheduling for Communication-Constrained Distributed Multi-Agent Systems

    cs.MA 2026-08 conditional novelty 5.0 of 10

    A multi-decoder graph attention policy trained with a critic-free group-relative gradient outperforms auction-based and prior learning baselines on communication-limited multi-agent task scheduling.

  8. Adaptation and Fine-tuning with TabPFN for Travelling Salesman Problem

    cs.LG 2025-11 conditional novelty 5.0 of 10

    TabPFN-v2, fine-tuned on one 500-node TSP sample in about two minutes, constructs TSP tours reaching 2-5% of Concorde optimality after 2-opt post-processing, across instance sizes 50 to 1000.

  9. Graph Optimization Foundation Model: Tokenizing Graph via A Language-Model Paradigm

    cs.LG 2025-09 reject novelty 5.0 of 10

    A per-graph BERT-style masked random-walk model is repurposed to generate shortest paths and tours, with mixed quality versus classical solvers and no cross-graph transfer evaluation.

  10. GES-TSP: Graph Edge Sparsification for TSP

    cs.AI 2026-06 conditional novelty 4.0 of 10

    GES uses Delaunay coarse graphs, hand-crafted edge features, and a GAT to sparsify Euclidean TSP instances, pruning ~95–99% of edges with sub-1% optimality gaps on MATILDA and TSPLIB.

  11. Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks

    cs.LG 2026-02 conditional novelty 4.0 of 10

    A 20-feature MLP predicts greedy optimality gaps for combinatorial auctions; a hybrid allocator routes hard 'whale-fish trap' instances to a GNN specialist, achieving 0.51% overall gap on synthetic mixed distributions.

  12. Graph Neural Networks are Heuristics

    cs.AI 2026-01 conditional novelty 4.0 of 10

    An unsupervised non-autoregressive GNN trained only on a differentiable Hamiltonian-cycle objective beats greedy nearest-neighbor on TSP100/200/500 and matches Christofides at millisecond speeds.

  13. A Comparative Review of Parallel Exact, Heuristic, Metaheuristic, and Hybrid Optimization Techniques for the Traveling Salesman Problem

    cs.DC 2025-05 reject novelty 3.0 of 10

    A literature review of parallel TSP solvers that introduces several unvalidated evaluation metrics for cross-paradigm comparison.

Pith tools