Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis +2
We consider a learning-augmented framework for NP-hard permutation problems. The algorithm has access to predictions telling, given a pair of elements, whether is before…
cs.DS2024
Improved FPT Approximation for Non-metric TSP
Evripidis Bampis, Bruno Escoffier, Michalis Xefteris
In the Traveling Salesperson Problem (TSP) we are given a list of locations and the distances between each pair of them. The goal is to find the shortest possible tour that visits…
cs.DS2024
Parsimonious Learning-Augmented Approximations for Dense Instances of -hard Problems
Evripidis Bampis, Bruno Escoffier, Michalis Xefteris
The classical work of (Arora et al., 1999) provides a scheme that gives, for any , a polynomial time approximation algorithm for dense instances of a family of $\mathc…