Circulation-Preserving Partial Coloring for Rounding Asymmetric Tour Relaxations

Solvers for the asymmetric traveling salesman problem (ATSP), where the cost of going from city $u$ to city $v$ can differ from the cost of going back, often start from a fractional plan. This is a matrix that says "use 0.6 of arc $u \to v$ and 0.4 of arc $u \to w$." They then have to turn that plan into an actual tour. That last step is where they break. Rounding every arc independently, or greedily committing to the largest entries, destroys the one property that makes a directed tour feasible: every city must have exactly one arc in and one arc out. Rounding also shatters the plan into many disconnected small loops, called subtours. We propose rounding the fractional plan the way discrepancy theory rounds fractional colorings. The rounding moves the fractional values in small random steps, and it only moves them in directions that keep in-flow equal to out-flow at every city. When an arc's value reaches 0 or 1 it is frozen for good. The process stops once about half the arcs are frozen, at which point the fixed path fragments are contracted into single nodes, the smaller instance is re-solved, and the procedure repeats.

This matters because the file shows a stark split. There is theory that guarantees constant-factor tours through very intricate machinery with constant 506. There are also fast continuous methods that beat LKH-3 on large random instances but decode their relaxations with greedy rounding and 2-opt, and give no guarantee. Iterative partial coloring is exactly the tool that combinatorics uses to round large systems of coupled constraints without cascading dead ends. It has never been applied to directed tour relaxations, where the coupled constraint is flow conservation.

Core Claim

We claim that a randomized partial-coloring walk confined to the circulation space of the free arcs can round a fractional ATSP solution with measurably fewer subtours and lower final cost than greedy or independent decoding. The circulation space is the set of arc-value changes that leave every city's in-flow minus out-flow at zero. The walk is interleaved with contraction and re-solving on the remaining half. We expect the advantage to be largest on strongly asymmetric instances.

The new ingredient is a potential that tracks, for a maintained family of directed cuts, how close each cut's crossing mass is to dropping below one. The walk step is biased away from that danger. Degree balance is therefore preserved exactly by construction, and subtour formation is controlled probabilistically rather than repaired afterward.

Concretely, let $x \in [0,1]^A$ be the fractional arc values and $F \subseteq A$ the arcs not yet frozen. Each step is

$$x \leftarrow x + \eta\, g, \qquad g \in \ker(M_F) \cap \{g : \langle \nabla \Phi(x), g\rangle \ge 0\},$$

where $M_F$ is the node–arc incidence matrix restricted to $F$, so $M_F g = 0$ means no city's in- or out-flow changes. $\eta$ is a step size, and $g$ is drawn as a random Gaussian direction projected into this cone. The potential is

$$\Phi(x) = -\sum_{S \in \mathcal{C}} \exp\!\big(-\lambda\,(x(\delta^+(S)) - 1)\big),$$

where $\mathcal{C}$ is the tracked cut family, $x(\delta^+(S))$ is the total mass leaving vertex set $S$, and $\lambda$ controls how sharply near-violated cuts are penalized. The walk freezes coordinates at the boundary of $[0,1]$, and each phase stops when $|F|$ halves.

Research Program

The method borrows from three places. The idea of restricting a random rounding walk to a linear subspace, while steering it with a smoothed potential, comes from Spectral Sparsification by Deterministic Discrepancy Walk. That paper walks in restricted subspaces under a smoothed max-eigenvalue potential to build singular-value sparsifiers for directed graphs. It explicitly cannot handle Eulerian (balanced-flow) sparsifiers, because its derandomized walk lacks a tool for the balance constraint.

Our setting reverses the difficulty. Flow balance is a linear subspace, so a randomized walk preserves it trivially. The genuinely hard constraint is the family of exponentially many cut conditions, which we handle through the potential rather than through a matrix-norm bound. The alternative of doing partial coloring by mirror descent, from A new framework for matrix discrepancy: partial coloring bounds via mirror descent, is a second instantiation we will compare against the Gaussian walk.

The "cautious rounds" philosophy comes from the nibble line. There, edges pick tentative colors, conflicts are discarded, and only a fraction is finalized per round, so the remaining options stay concentrated. This appears in Near-Optimal, Distributed Edge Colouring via the Nibble Method and in the constant-update-time purging of Nibbling at Long Cycles. Those works color undirected edges under a proper-coloring constraint. We transfer only the pacing and the concentration logic, not the constraint.

The fractional input comes from two sources. The first is the Held-Karp LP solved by cutting planes, which supplies the cut family $\mathcal{C}$ for free as the separated cuts. The second is the doubly stochastic output of Solving the Asymmetric Traveling Salesman Problem via Trace-Guided Cost Augmentation. That method optimizes over doubly stochastic matrices with a trace penalty against directed cycles, then decodes greedily and polishes with 2-opt. Its relaxation is non-convex and its decoding step is exactly what we replace.

The motivating theory is A constant-factor approximation algorithm for the asymmetric traveling salesman problem. That paper shows that single-shot rounding of directed relaxations fails on subtours, and that progress required recursive, hierarchical treatment of nested clusters. Our recursion, which halves the free arcs, contracts, and re-solves, is a far simpler and empirical cousin of that hierarchy. We make no claim to match its guarantee.

The analytical target is modest and checkable. We aim to show that each phase preserves in/out-degree exactly. We also aim to show that, with a potential-controlled step, the expected number of tracked cuts whose crossing mass collapses to zero per phase is bounded, so that the cycle cover after all $O(\log n)$ phases has few components. The $O(\log n)$ phase count follows because each phase halves the free arcs.

The tension noted in the file between linear discrepancy and non-associative battery-capped routing, raised by Optimal energetic paths for electric cars, does not bite here. ATSP tour cost is additive and flow conservation is linear. That paper does tell us not to extend the method to energy-capped routing without a new idea, and we will not.

Baselines

The naive reference point is Birkhoff/assignment decoding. We take the fractional matrix, extract the maximum-weight permutation (a cycle cover), and patch its subtours by cheapest arc exchange. We run it on exactly the same fractional inputs as our method, so it isolates what rounding adds when the relaxation is held fixed.

The strongest existing method is the trace-guided cost augmentation of Zhang, Shi, and Lee. On 1,000-node random ATSP it reports "-21.40% Avg. GAP" relative to LKH-3, a 21.4% improvement in tour quality. On 500-node instances it reports roughly 0.87 seconds against nearly 30 seconds for LKH-3. We will run their pipeline end to end on the same instances, and also swap only their decoder for ours, keeping their relaxation, 2-opt polish, and wall-clock budget identical.

LKH-3 is the classical reference. Because the reported gap is measured against LKH-3 under the authors' settings, we will rerun LKH-3 ourselves under two budgets: matched wall-clock time and generous time. This tells us whether the 21.4% reflects under-budgeting. Beating the strongest baseline means a lower mean tour cost than Zhang et al. at equal wall-clock on ATSP1000, with a paired test across instances. It also means fewer subtours before any local-search polish.

Two ablations isolate the key ingredient. The first runs the same walk with $\lambda = 0$, meaning no cut potential, only degree preservation. The second runs deterministic fix-and-resolve: it freezes the top half of arcs by fractional value, contracts, and re-solves, with no random walk.

Why not just…?

Why not just polish the relaxation's greedy decoding with LKH-3 or 2-opt? Local search can repair a bad decoding, and on small instances it may erase any difference between decoders. That is a real threat. The evidence that it is insufficient at scale is the reported behavior of LKH-3 itself, which took nearly 30 seconds on 500 nodes and trailed the trace method by 21.4% on 1,000 nodes, per Zhang et al.. We settle it by reporting cost both before and after an identical polish budget. If our advantage vanishes after polishing, the claim reduces to "a better warm start," and we will say so.

Why not just fix the largest arcs, contract, and re-solve? This greedy iterative rounding is the most dangerous alternative, because it shares our recursion and differs only in how arcs get frozen. Our argument is that greedy fixing commits correlated arcs together and so tends to close small loops. The random circulation walk spreads commitments while keeping balance, and the potential guards cuts. The deterministic fix-and-resolve ablation tests this directly. If it matches our method, we drop the walk and publish the recursion as the contribution.

Why not just round each arc independently, or sample a permutation from the Birkhoff decomposition? Independent rounding breaks the in/out-degree constraint outright. Permutation sampling keeps degrees but ignores cuts, which is the single-shot failure mode that Svensson, Tarnawski, and Végh identify for directed relaxations. The assignment-decoding baseline and the $\lambda = 0$ ablation measure exactly how much the cut potential buys over degree preservation alone.

Why not just train a neural solver? The file reports that learned solvers trained on symmetric or Euclidean data fail when costs become asymmetric, per Zhang et al.. It also reports that multi-distribution robustness requires very large meta-pretraining, per Omni-VRP. We include an Omni-VRP model applied to our instances only as a secondary reference, not as the main competitor.

Proposed Experiments

The primary benchmarks are the synthetic ATSP500 and ATSP1000 random instances used by Zhang et al., together with their triangle-inequality ATSP variant and TSPLIB asymmetric instances. For TSPLIB, no reported per-instance result was found on Lacuna, so we will generate all baseline numbers ourselves.

We add a controlled asymmetry sweep. Costs are set to $c(u,v) = (1-\alpha)\,s(u,v) + \alpha\, r(u,v)$, with $s$ a symmetric metric, $r$ an independent random matrix, and $\alpha \in [0,1]$ controlling how directional the costs are. This sweep tests the specific prediction that the gap between circulation-preserving rounding and greedy decoding grows with $\alpha$.

The metrics are final tour cost relative to the best known or LKH-3 long-run solution, the number of subtours in the cycle cover before patching, wall-clock time, and variance across random seeds. For the Held-Karp input we also report the ratio of tour cost to LP value, which is an empirical integrality-gap proxy.

The decisive check has two parts. On ATSP1000, swapping only the decoder inside the Zhang et al. pipeline must lower mean tour cost at matched time. Our method must also beat the deterministic fix-and-resolve ablation by a margin larger than seed variance. If either part fails, the random circulation walk is not earning its place.

A second check verifies the mechanism rather than the outcome. Along the walk we will log the minimum tracked cut mass. Our explanation predicts that runs with $\lambda > 0$ keep it bounded away from zero far more often than $\lambda = 0$ runs, and that this frequency predicts the final subtour count.