AI Paper Atlas

Research map / Learning theory and algorithms / Sample complexity

Alternative Filtering for the Weighted Circuit Constraint: Comparing Lower Bounds for the TSP and Solving TSPTW

Sylvain Ducomman, Hadrien Cambazard, Bernard Penz

AAAI 2016 · Learning theory and algorithms › Sample complexity · approach: Computational thresholds in graphs and structure · 16 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
use exact reduced costs instead of LP reduced costs for assignment filtering (ablation)Assignment filtering · TSPLIB ATSPsearch nodes: 1175424,4 -> 4852,3Improved
Held and Karp filtering instead of ln-pathCP TSP model · TSPLIB ATSProot gap (%): 6,3 -> 1,0Improved
ln-path instead of Held and KarpCP TSPTW model · Dumas TSPTWroot gap median (%): 2,00 -> 0,72Improved
ln-path instead of Held and KarpCP TSPTW model · Ascheuer TSPTWroot gap mean (%): 0,76 -> 0,50Improved
ln-path instead of Held and KarpCP TSPTW model · Pesant TSPTWroot gap mean (%): 4,71 -> 5,06Hurt
ln-path instead of assignment boundCP TSP model · TSPLIB ATSProot gap (%): 15,0 -> 6,3Improved
ln-path instead of Held and KarpCP TSP model · TSPLIB ATSPtime (s): 25,7 -> 426,9Hurt
ln-path instead of Held and KarpCP TSPTW model · Ohlmann TSPTW (150/200 vertices)cpu time: 10,02 -> 45,54Hurt
ln-path instead of Held and KarpCP TSPTW model · Dumas w80 exact solveinstances solved: 18/20 -> 18/20No clear effect
ln-path instead of assignmentCP TSPTW model · Dumas w80 exact solveinstances solved: 12/20 -> 18/20Improved
ln-path instead of Held and KarpCP TSPTW model · Ascheuer exact solveinstances solved: 29/50 -> 35/50Improved

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy