2 papers
cs.DS2026
TSP with Predictions: Heatmap to Tour with Provable Guarantees
Marek Eliáš, Fabrizio Grandoni, Adam Polak +1
The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent effor…
cs.DS2026
Warm-Starting All-Pairs Shortest Paths with Predictions
Adam Polak, Jonas Schmidt
One of the three key hypotheses of fine-grained complexity asserts that computing All-Pairs Shortest Paths (APSP) requires cubic time, up to subpolynomial factors, in the worst cas…