Michalis Xefteris — accepted AI-conference papers

2025

Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems

Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis, Panagiotis Patsilinakos, Michalis Xefteris

ICML 2025poster

We consider a learning augmented framework for NP-hard permutation problems. The algorithm has access to predictions telling, given a pair $u,v$ of elements, whether $u$ is before $v$ or not in an optimal solution. Building on the work of Braverman and Mossel (SODA 2008), we show that for a class of…

Cited by 2 Source ↗PDF ↗Scholar ↗

2024

Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems

Evripidis Bampis, Bruno Escoffier, Michalis Xefteris

ICML 2024poster

The classical work of (Arora et al., 1999) provides a scheme that gives, for any $\epsilon>0$, a polynomial time $1-\epsilon$ approximation algorithm for dense instances of a family of $\mathcal{NP}$-hard problems, such as Max-CUT and Max-$k$-SAT. In this paper we extend and speed up this scheme usi…

Cited by 4 Source ↗PDF ↗Scholar ↗