Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems
Authors: Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis, Panagiotis Patsilinakos, Michalis Xefteris
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 unknown fixed optimal solution. Building on the work of Braverman and Mossel (SODA 2008), we show that for a class of optimization problems including scheduling, network design and other graph permutation problems, these predictions allow to solve them in polynomial time with high probability, provided that predictions are true with probability at least 1/2+ϵ, for any given constant ϵ > 0. Moreover, this can be achieved with a parsimonious access to the predictions. [...] In this paper, we design learning-augmented algorithms for NP-hard optimization problems. [...] We design a novel framework which is capable of handling permutation optimization problems that exhibit one of two key properties: the decomposition property and the c-locality property in their objective function (see Section 3 for formal definitions). [...] The proof of Theorem 1.1 demonstrates that, for the permutation problems under consideration, knowing an approximation of each σ (i) (in an optimal solution σ ) within an additive O(log n) bound is sufficient to solve the problem in polynomial time. In Section 5, we first show that this O(log n) approximation is not always sufficient for polynomial time solvability. Finally, we prove that the O(log n) bound is tight, as there are decomposable and c-local problems where an additive approximation of f(n) log n is not enough to solve these problems in polynomial time, for any unbounded function f. |
| Researcher Affiliation | Academia | 1Sorbonne Universit e, CNRS, LIP6, F75005 Paris, France 2National Technical University of Athens, Greece 3Archimedes, Athena Research Center, Greece 4Universit e Paris-Dauphine, Universit e PSL, CNRS, LAMSADE, 75016, Paris, France 5Athens University of Economics and Business, Athens, Greece. |
| Pseudocode | No | The paper describes dynamic programming algorithms in Lemmas 4.1 and 4.2 but does not present them in a formal pseudocode block or algorithm listing. |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and proofs for NP-hard permutation problems. It does not conduct experiments with specific datasets, therefore, no information on open datasets is provided. The paper discusses the framework in general terms related to prediction models but does not use datasets for empirical validation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments on specific datasets. Therefore, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and proofs. It does not describe any experiments that would require specific hardware for execution. |
| Software Dependencies | No | The paper is theoretical and does not report on experimental results that would rely on specific software dependencies and versions. Therefore, no such information is provided. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and proofs without conducting empirical experiments. Therefore, it does not provide details on experimental setups, hyperparameters, or training configurations. |