# Divide and Conquer Networks

arXiv: https://arxiv.org/abs/1611.02401 · HTML: https://mlsanity.com/paper/1611.02401/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2016.

## Built on by (most cited first, 6 of 6)

- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem](https://mlsanity.com/paper/2501.13767/) (2025)
- [Reinforcement Learning-based Non-Autoregressive Solver for Traveling Salesman Problems](https://mlsanity.com/paper/2308.00560/) (2023)
- [Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks](https://mlsanity.com/paper/2302.04035/) (2023)
- [SEAFormer: A Spatial Proximity and Edge-Aware Transformer for Real-World Vehicle Routing Problems](https://mlsanity.com/paper/2601.19395/) (2026)

## Abstract (arXiv)

We consider the learning of algorithmic tasks by mere observation of input-output pairs. Rather than studying this as a black-box discrete regression problem with no assumption whatsoever on the input-output mapping, we concentrate on tasks that are amenable to the principle of divide and conquer, and study what are its implications in terms of learning. This principle creates a powerful inductive bias that we leverage with neural architectures that are defined recursively and dynamically, by learning two scale-invariant atomic operations: how to split a given input into smaller sets, and how to merge two partially solved tasks into a larger partial solution. Our model can be trained in weakly supervised environments, namely by just observing input-output pairs, and in even weaker environments, using a non-differentiable reward signal. Moreover, thanks to the dynamic aspect of our architecture, we can incorporate the computational complexity as a regularization term that can be optimized by backpropagation. We demonstrate the flexibility and efficiency of the Divide-and-Conquer Network on several combinatorial and geometric tasks: convex hull, clustering, knapsack and euclidean TSP. Thanks to the dynamic programming nature of our model, we show significant improvements in terms of generalization error and computational complexity.