Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems
Authors: Evripidis Bampis
Bruno Escoffier
Dimitris Fotakis
Panagiotis Patsilinakos
Michalis Xefteris
Venue: ICML 2025 poster (2025)
Keywords: Learning-augmented algorithms
NP-hard permutation problems
predictions
Primary area: theory->optimization
TL;DR: The articles shows that a class of NP-hard permutation problems are polytime solvable when enhanced with predictions (correct with some probability bound) on an optimal permutation.

Abstract: 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 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+\epsilon$. Moreover, this can be achieved with a parsimonious access to the predictions.

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
Evripidis Bampis'
Bruno Escoffier Dimitris Fotakis 23 Panagiotis Patsilinakos" Michalis Xefteris
Abstract
troduced by Mahdian, Nazerzadeh, and Saberi, who applied it to the problem of allocating online advertisement space for budget-constrained advertisers (Mahdian et al., 2007). Later, Lykouris and Vassilvitskii formalized the framework, studying the online caching problem using predictions (Lyk- ouris & Vassilvitskii, 2021). The main emphasis in the field of algorithms with predictions has been on online optimiza- tion, as predicting the future of partially unknown input instance is natural approach. However, in the past few years, the field has expanded into various other areas. An almost complete list of papers in the field can be found in (I Lindermayr & Megow).
We consider a learning-augmented framework for NP-hard permutation problems. The algorithm has access to predictions telling, given pair u, v of elements, whether u is before u or not in an unknown fixed optimal solution. Building on the work of Braverman and Mossel (SODA 2008), we show that for 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 least 1 1/2+ + e, for any given constant 0. Moreover, this can be achieved with a parsimonious access to the predictions.
More relevant to this work, algorithms with predictions have been used to address NP-hard optimization problems and overcome their computational challenges. The first learning- augmented algorithms applied to NP-hard problems were fo- cused on clustering, as seen in (Gamlath et al., 2022; Ergun et al., 2022: Nguyen et al., 2023), and other graph optimiza- tion problems (Chen et al., 2022). Moreover, several papers have studied MAXCUT with predictions, including (Bampis et al., 2024; Cohen-Addad et al., 2024; Ghoshal et al., 2024; Dong al., 2025). Cohen-Addad al. investigated the approximability of MAXCUT with predictions in two mod- els (Cohen-Addad et al., 2024). In the first model, similar to the one used in this work, they assumed predictions for each vertex (on its position in an optimal cut) that are correct with probability 1/2 + e, for a given e > O, and presented a polynomial-time (0.878 + (a(")))aapproiimattion algorithm. In the second model, they receive a correct prediction for each vertex with probability >> 0 (and no information oth- erwise) and designed a (0.858 + R(c)) -aaaproxximation algo- rithm. Ghoshal et al. also studied MAXCUT and MAX2-LIN in both models (Ghoshal et al., 2024). Furthermore, (Braver- man et al., 2024) studied Maximum Independent Set within the framework of Barning-augmentt the aforementioned first model. Finally, (Antoniadis et al., 2024) studied approximation algorithms with predictions for several NP- MP-hard optimization problems within a prediction model different from the one used in this work.
1. Introduction
In recent years, advancements in Machine Learning (ML) have significantly influenced progress in solving optimiza- tion problems across a wide range of fields. By leveraging historical data, ML predictors are utilized every day to tackle numerous challenges. These developments have motivated researchers algorithms to incorporate ML predictions into algorithm design for optimization problems. This has given rise to the vastly growing field of learning-aueen augmented algo- rithms, also known as algorithms with predictions. In this framework, it is assumed that predictions about a problem's 's input are provided by a black-box ML model. The objective is to use these predictions to develop algorithms that out- perform existing ones when the predictions are sufficiently accurate.
The idea of auggeetee algorithms was initially in-
"Equal contribution 'Sorbonne Université, CNRS, LIP6, F. 75005 Paris, France "National Technical University of Athens, Greece "Archimedes, Athena Research Center, Greece "Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, 75016, Paris, France Atthens University of Beonomics and Business, Athens, Greece. Correspondence to: Michalis Xefteris <mxef- teris hotmail.com.>.
algorithms,, adopting
In this paper, we design Sarning-auugentee algorithms for NP-hard optimization problems. Our approach does not use all available predictions for the problem at hand but instead utilizes the predictor selectively. This aligns with the con-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
cept of parsimonious algorithms, introduced by (Im al., 2022), which aim to limit the number of predictions used, assuming that obtaining additional predictions can be com- putationally expensive. Here, we consider problems whose feasible solutions can be represented as permutations. There are n input elements for an optimization problem denoted by 01,.... On A permutation (ordering) a corresponds to the solution (do(1)..... ar(n))
welfare maximization in keyword auctions with externali- ties and window size representatives of c-local problems. All these are well-known NP-hard problems and cannot be solved exactly in polynomial time without predictions unless P = NP (deterministic), or NP C BPP (random- ized). Moreover, the framework can naturally be extended to address a variety of other NP-hard problems with similar structural properties.
Regarding the prediction model, we adopt the following probabilistic framework. For each pair i, we can get prediction query q(a,,a) a,) that denotes whether a, precedes aj or not in a fixed optimal solution (permutation). Each prediction is independently correct with probability at least 1/2+ + e, for a given constant 6 > 0. An algorithm has access to (*) predictions. A formal description of the model is given in Section 2.
Another important aspect of our framework is that it does not query all possible pairs but instead makes only O log n) queries, making it parsimonious with respect to the num- ber of predictions used. We note that this is a tight bound on the number of queries, as 22 log n) queries are nec- essary even the case of perfect predictions already for the Noisy Sorting Without Resampling problem (see Sec- tion 2.1). Indeed, it becomes sorting by comparisons (where comparisons are queries), for which it is well known that 22(n log comparisons are needed (even for randomized algorithms).
In this work, we use these prediction queries to solve NP- hard optimization problems exactly with high probability. We design a novel framework which is capable of han- dling 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 permu- tation problems under consideration, knowing an approxi- mation of each o" (i) (in an optimal solution a²) within an additive Ollog n) bound is sufficient to solve the problem in polynomial time. In Section 5, we first show that this Olognn approximation is not always sufficient for polyno- mial time solvability. Finally, we prove that the O(log n) bound is tight, as there are decomposable and c-local prob- lems where an additive approximation of f()) log is not enough to solve these problems in polynomial time, for any unbounded function f-
The decomposition property states that solving subprob- lem I(i, j) (between positions i and in the permutation) of the optimization problem at hand optimally depends only on the set of elements in positions in [i, the permutation (i..)) j) of these elements in j]. and the set of elements to the left of i and the right of j. but not their order. On the other hand, the c-locality property states that the cost function of the problem depends only locally (with respect to the permutation) on pairs of distinct elements.
We conclude this section by brief discussion on the pre- diction model. Similarly as several recent articles on the topic, our framework requires good predictions of optimal solutions for hard optimization problems, which is a strong assumption. Whether ML algorithms are or will soon be able to provide such good predictions or not is currently an open question, and large number of recent works do focus on getting predictions for discrete optimization problems (see (Bengio et al., 2021; Cappart et al., 2023) for survey- like papers, and (Khalil et al., 2017) for a specific work on predictions for problems including (Euclidean) TSP). This recent but fast-growing field makes it reasonable to hope for some accurate predictors for some permutation problems in the near future. We note also that there are restricted settings where one could outline how such noisy predictions of the optimal permutation can be learned. E.g., consider setting where instances are stationary and instance stationarity im- plies that the optimal solution / permutation of each instance is a noisy sample from a Mallows distribution M(T", .8) with n² corresponding to the optimal permutation of the "mean" instance and the noise parameter 3 accounts for the variance of the instance distribution. Such a Mallows dis-
More specifically, we adjust and extend the approach of Braverman and Mossel (Braverman & Mossel, 2008; 2009) for the problem of sorting from noisy information and give the following theorem for a family of optimization problems (see Section 4 for its proof).
Theorem 1.1. If the objective function of a permutation optimization problem P either exhibits the decomposition property or is c-local, then P can be solved exactly with high probability in polynomial time, using Onn log n) prediction queries.
Therefore, if permutation optimization problem is either decomposable or c-local, it can be solved with high proba- bility in polynomial time within our prediction-basee basedd frame- work. We note that the running time depends on the accu- racy of the prediction queries, i.e., on e. To illustrate these properties, we examine several example problems: Max- imum Acyelic Subgraph, Minimum Linear Arrangement, a scheduling problem as examples of decomposable prob- lems, the Traveling Salesperson Problem (TSP) and social
2

---

Polynomial Time Learning-Augmenteed Algorithms for NP-hard Permutation Problems
tribution M(=,,9 .33 can be learned from instances sampled independently from the instance distribution (Busa-Fekete et al., 2019). Samples from M(x*, ,9) can be used as pre- dictions in the form of noisy rankings. For fixed 8 this provides whp a sufficiently good approximation of the rank- ing (up to an additive (log n) term on the position of each element) so that our approach applies (see (Braverman & Mossel, 2009), where this case is discussed).
the element of A that is in position i in the permutation (i.e., the permutation is (Aa(1); (L)()))00()) -::)::---..::::. "...:-..a)))))) (a(n))) To deal with feasibility constraints, fr(a) = oo if o is unfeasible (for minimization problem, -oo for a maximization problem).
A core part of our work will focus on permutation problems for which we have an additional information, which is an approximation of o² (i) for an optimal solution o². We formalize this in the following definition.
Definition 2.3. Given permutation problem P and per- mutation (a1, d2...., an), P is k-position enhanced if we know that there exists an optimal solution o* such that for all i, la (i) -l S k.
2. Background and Overview
2.1. Definitions
Formally, we consider the following probabilistic prediction model, which is inspired by the noisy query model studied in (Braverman & Mossel, 2008).
2.2. Framework Overview
The NSWR problem has been introduced and studied in (Braverman & Mossel, 2008). They showed the following result.
Definition 2.1. Let A = fai..... an and o² be a permu- tation from 1,,7] to [1. n.. For each pair (ay; at) in (2) the result of a prediction query for (ae, ae), with respect to o². is q(ae; ae) E { {-1,1} where q(ae, ae) -q(at: ae). We assume that:
Theorem 2.4. (Braverman & Mossel, 2008) There exists a randomized algorithm that for any a > 0 finds an optimal solution NSWR (s-optimal) with p 1/2 c,c >> 0 in time n ([[++1) ") except with probability n Moreover, the algorithm asks O(n n) queries.
for each 1 S j S n the probability that q(ar(()): a (r) (1)) = 1 is at least 1 +. 0 < 1/2,
the queries {g(ae, at): : 1 S l < < n} are inddpen- dent conditioned on o².
The proof of this theorem mainly relies two results. The first one shows that with high probability an optimal so- lution मt' of NSWR (s-optimal) is close to the "hidden" permutation a².
In this definition, the query g(oe, ar) asks whether aı pre- cedes a, in (1))----- - :gg (m)) not. The first item states that the prediction is correct with probability at least 1/2+ e..
Theorem 2.5. (Braverman & Mossel, 2008) Consider the NSWR problem, with p = 1/2 + e,e > O, with respect to a permutation o* and let n² be any s-optimal order assuming that q satisfies Definition 2.1. Let a > 0. Then there exists constant c(ac,e) such that except with probability On -a) it holds that
Given the prediction queries, we are interested in finding permutation that maximizes the number of agreements with the queries. Formally:
Definition 2.2. Given (z) prediction queries q(ag, az). the score (T) of permutation क : [1,n] - [1,m] is given by
max la (0(() -
TT (3) S e log n = Olog
Sq (T) Σ ((()))),a+))). icj
(1)
The second result is a dynamic programming (DP) algo- rithm showing that k- k-position enhanced NSWR is solvable in ((20(k),,²) Then specific iterative procedure allows for the computation of an optimal solution of NSWR. Very roughly speaking, the use of queries allows for a k-position enhancement for NSWR with k = O(log n) (thanks to The- orem 2.5), and then the DP algorithm works in polynomial time ((20()) = (1))
We say that permutation x² is s-optimal if nt is maxi- mizer of (I) among all permutations.
The Noisy Sorting Without Resampling (NSWR) problem, defined in (Braverman & Mossel, 2008), is the problem of finding an s-optimal permutation x² with respect to a (hid- den) permutation a² assuming that q satisfies Definition 2.1 with p 1/2 /2++2., c, 0.
In this work, we build upon these results to tackle various problems in our prediction setting. Roughly speaking, our framework first generates warm-start solution using the prediction queries and then utilizes this solution to solve the problem with dynamic programming. The idea of leveraging predictions to obtain a warm-start solution has been explored in a series of papers in the literature (Dinitz et al., 2021; Sakaue & Oki, 2022). The following lemma, which makes a
As mentioned in the introduction, consider in this work permutation problems, i.e., optimization problems whose solutions of an instance I are permutations of n elements of a set A of I (vertices or edges in a graph, jobs in a scheduling problem....) )) So the goal is to maximize or minimize fr(a) for : [1,m] + [1, n). Here, (o()) E A is
3

---

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
connection with the aforementioned results on NSWR, will allow us get the polynomial time algorithms claimed in Theorem 1.1.
ordering. Roughly speaking, our decomposition property holds when finding and ordering elements from positions i to j only depends on the set of elements before i and after j. not on their particular ordering.
Lemma 2.6. Suppose that a k-position enhanced version of permutation problem P is solvable in polynomial time for k- = O(log n). Then P can be solved exactly in polyno- mial time with high probability, using On log n) prediction queries.
We now formalize this idea, and illustrate it on three dif- ferent problems. For a permutation a : [1. nl + [1. n²). we denote a (i. the subpermutation of on [i. S. (i. the set {or ................................ {{}} (indices in positions between and j), (k) 5, k) (first k indices, L stands for left) and (k) S. (k, n)) (indices in position between k and n, I stands for right).
Proof. Let o" be an optimal permutation for an instance of the optimization problem P. By making On log n) queries, according to Theorem 2.4 we can get in polynomial time with high probability an optimal solution n² for the NSWR problem relative o².
Definition 3.1. Let P be a permutation problem, with ob- jective function f. We say that P fulfills the decomposition property if there exists a function g such that:
From Theorem 2.5, we know that with high probability (o*(1) x +i)) = Ollog n) for all i. Equivalently, for all j:
fI(0) = g gl,,,,,100 n,0,0.))
lo' ( - ا| = Ollogn).
For anrany/ i j in f1..... n and permutation a:
I Lo - 1), R, (j (i,)))
As by assumption the k-position enhanced version of P is solvable in polynomial time for h = O(logn), we can find o² n -1 hence o², in polynomial time.
g s, (s
g(s + L.). Ro +g(++ 1(
(1 R. + 1), S., +1,)),
Motivated by Lemma 2.6, we exhibit two sufficient condi- tions for a permutation problem to be polynomial time solv- able when being k-positioned enhanced, for h = (log n)). These conditions (decomposabilitty and c-locality) and their illustration on classical optimization problems are given in Section 3. The proof' that under these conditions Oloog n)) positioned enhanced permutation problems are polynomial time solvable are in Section 4. They are based on DP al- gorithms, one of which being a generalization of the one of (Braverman & Mossel, 2008).
for some function h.
Note that h does not depend on the permutation of any el- ements, only on sets of elements. In this definition, we express the objective function on subproblem (i.j) by a function y that depends on the subpermutation (i,j) be- tween and j and on sets (not positions) of elements before and after j (Lo 1) and Ro [j + 1)).
The decomposition property states that the value is the sum of the value on the subproblem (i, s) (referred to as the "left call" in the sequel), the value on the subproblem (s + 1, (referred to as the "right call"), and a quantity (function h) that depends only on the sets (not the ordered sets) of elements involved in the decomposition.
3. Decomposability and c-locality
We now give the definitions for the decomposition property and c-locality, and illustrate them with some problems ex- pressible in these ways. As explained before, each of these properties will allow to design DP algorithms, which is the key step to derive Theorem 1.1.
Maximum Acyelic Subgraph. In the Maximum Acyelic Subgraph problem, we are given a simple directed graph
G G=(VE The goal is to find a permutation a [1, nl + [1.n] which maximizes f(a) = [((a())) va(n) E E ::: << jH. This is a well known NP-hard problem (Karp, 1972).
3.1. Decomposition property
To design DP algorithms, we will consider subproblems. Intuitively, for i < j we will consider subproblems of finding and ordering elements in positions to j. i.c., (dr()))...; and need a recurrence that allows express- ing the subproblem between i and j as a combination of the subproblems between and 8, and between 8 + 1 and j (for < 3 < j). A difficulty is that finding and order- ing elements from positions to j typically depends on the elements before (between positions and - 1) and after (between positions j + 1 and n), and on their respective
As this problem only depends on the relative order of ele- ments (endpoints of arcs) and not on their exact position, it is easy to express it in the form of Definition 3.1. For given < j and (i. we simply define:
g(i.j. L. R. (i. = H(va(e), Pa()) E (e:iSerrsan
This is just the number of arcs "well ordered" by a with both endpoints between positions and j (g is independent
4

---

Polynomial Time Learning-Augmennedd Algorithms for NP-hard Permutation Problems
of L and R). Obviously the first item of Definition 3.1 is verified (for = 1 and j = n count the total number of ares "well ordered by o).
Similarly, for edge with one endpoint in the right part Ra(i + 1) and one endpoint in (i,j) i.e., (Uo(e))oo(r) with i S l S and j < r, we will charge only for this edge the (yet partial) contribution j - f. Let N3 be the sum of these contributions (note that Ng depends only on Ro (j + 1) and (i)
For the second item, g(i, s, ( (i, (resp. g(s + 1, (s), R. (j + ( (s+ counts the number of ares well ordered by a with both endpoints in positions between and s (resp. between s + and j). So, to get g(i, Lo 1), Ro [j +1), (i,,))) we only have to add arcs (B)) va(r)) with - l S and + + S. j. In other words, if we denote cul(A, A, B) the number of ares (ve, U,) with f E A and r E B, we have
We then define g Lo (i R. Ro N2 + N/.
N1
12
l
Ro S. - (e
Note that this immediately generalizes to any problem whose objective function only depends on the relative order of endpoints of ares (for instance the weighted version of Maximum Acyclic Subgraph), not on their exact positions.
T
Figure I. Contribution in g of edges, depending on the positions of their extremities. The contribution is in solid line. If L < i and > j the contribution O.
Minimum Linear Arrangement. Let G (V, be a simple undirected graph. Given a permutation o : [1.n] + [1, nl], let call the weight of an edge as the absolute dif- ference between the positions assigned to its endpoints in a. Minimum Linear Arrangement is well known NP- hard (Garey& & Johnson, 1979) problem which consists of finding a permutation of the vertices of G such that the sum of the weights of its edges is minimized. More formally, we would like to find a permutation a : [1, - [1,n] that minimizes Σ (voot))"o)))) li - i/.
It is clear that the first item of Definition 3.1 is satisfied (when = 1 and j n, N1 equals the objective function, N₂ = N3- = 0).
For the second item, let i < 8 < j. Consider an edge (Vo(s) Po(r)]- We show, for each possible case, how to recover the contribution of this edge subproblem (i. (i.e., in g(i, j, Lo 1), Ro + 1), (i),)),,)) see Figure 2 for an illustration:
While Maximum Acyelic Subgraph deals (only) with the order of endpoints of ares the permutation, Minimum Lin- ear Arrangement depends on their exact position. We now show that the decomposition property also allows to deal with such a problem. The idea is the following: consider i < j. and fix the subpermutation a (i,,), j), the sets (i
If both é and r are in [ 8], its contribution in g (i- Ro (j+1), ((. is already counted in the "left call" g(i, s, Li - 1). (s + a(, s)).
Similarly, if both E and are in [s + 1, its contribu- tion in g(i, j, Li - 1), Ro (j + 1), (i. is already counted in the "right call" g(s + 1, L.) (j + 1), + 1,5)).
of elements "on the left", and R2 (j + 1) of elements "on the right". Then (see Figure for an illustration of the contribution of edges):
for an edge with both endpoints in So (i, we know its exact contribution (as o(i,j) is fixed). These edges have a global contribution N₂ (ene |r- E). Note that N₁ depends only on (i.
If S S s and s +1 r j, then the contribution is (s E) in the left call and A r- (s + 1) in the right call, so in total r - t 6.1. 1. It only missed 1 to get the correct contribution r f. So for these edges we have to add in total a contribution C₁ = cut(S (1, s), So (s + 1,))).
If < and S r S s, then the contribution on the left call is r r- i, the correct one. Similarly, if s 1 < E & j and + 1 < r the contribution of the right call is the correct one (j- - E).
For an edge with one endpoint in the left part La (i- 1) and one endpoint in (t. i.e., {Ua(e), Ba(r)) with f < i and < r < j. we will charge only for this edge the (yet partial) contribution r - (instead of r E, as the exact left position is not fixed yet). Let N₂ be the sum of these contributions (note that N2 depends only on Top (i - 1) and (i. j)).
and s + S r S j. the contribution in the left call is 0, the one in the right call is r (s + 1). misses 8 + 1 to get the correct contribution i.
If l <
5

---

Polynomial Time Learning-Augmennte Algorithms for NP-hard Permutation Problems
So for these edges we have to add in total C22 (s
3.2. c-locality
1- i) cut( T (i- 1), (s 1,))-
The c-locality property states that the cost function of the problem depends only locally (with respect to the permuta- tion/solution) on pairs of distinct elements. More formally, we have the following definition.
Similarly, i < f S and > j. to get the correct 8)).
charge we miss C33 = (j s) cut( R.
Definition 3.2. Let P be permutation problem, with cost function f. We say that P is c-local if, on an instance I asking for a permutation a on a set A = {ai...., an):
Then, we define h(La (i - 1), R2 + 1), (), S 1. = C1 + C2 + C3.
fI(0) = Σ (ostt((o(t-)) 0o((-o+1))--- ())))
n.
T
F
for some cost function' costr.
T
e
r
TSP. Given a complete graph on set V of vertices and a distance function d(v,, 22) on pair of vertices, TSP asks to find permutation or that minimizes E d(vo(s)- Ro((+))) (where (n(++)) is (o())) This NP-hard problem (Garey & Johnson, 1979) is then trivially 1-local (we can easily reformulate to get rid of the last term d(va(n)) (r(1))
Other routing problems can be shown to be 1-local as well.
Figure 2. Decomposition in g: blue (resp, orange) corresponds to the contribution in the left call (resp. right call), red corresponds to missing contributions (that are counted in lt). If é i and r j the contribution is O.
Social Welfare Maximization in Keyword Auctions with Externalities. In standard Keyword Auctions (Edelman et al., 2007; Varian, 2007), a set N = (1....,n) n.] of adver- tisers compete over a set K = {l,.... k} of advertisement (or simply ad) slots, where k S n. Each player i E N has valuation v, per click and their ad has an intrinsic click probability q: E (0, 1]. Each slot
Single-machine Sum of Completion Time Problem. We consider the following scheduling problem (denoted 1|prec| Σ Cj in the classical Graham's 's notation for schedul- ing problems), known to be strongly NP-hard (Lawler, 1978): we are given set of n jobs and a set of precedence constraints forming a DAG (J, The goal is order the jobs, respecting precedence constraints, as to minimize the sum of completion time of jobs.
K is associated with tlick-through rate (ctr) Aj. with 1 2 Å > X2 > A >> 0. The overall ctr of an ad i in slot is \y%. In the follow- ing, we assume that k = n, i.e., the number of slots k is equal to the number of ads n, for simplicity, by setting AR+1 = =... An = in case where < n.
We aim to compute an assignment π. : N - K of ads to slots (which for k is a permutation of ads) that the resulting expected social welfare, which is Ei=1 (2 is maximized.
Consider i < j, (i, j)) and (i-1). With this information, we can compute the completion time of each job in S. ji (as we know the jobs before them (Lo (i - 1)) and the order ati.) j) of jobs in (t, So we simply define g as the sum of these completion times (g depends on (i, and Lo (i- 1)), with of course value oa if the order (i. violates any constraints.
In Keyword Auctions with Externalitics (Gatti et al., 2018; Fotakis et al., 2011), the overall click-through rate of an ad i appearing in slot (1) also depends on the ads appearing in the e slots above (ii) - c, =(i) c+ 1,..., T(6) 1, where is known the window size and quantifies the scope of users' attention and memory when they process the ad list (Athey & Ellison, 20. We let Q:(T)) denote the i's ctr given the influence of the e ads above in æ. Then, we aim to compute an assignment ग N + [i]] of ads to slots so that the resulting expected social welfare under externalities, which is Σn P. (T),, is maximized.
Item I of Definition 3.1 is trivially satisfied. For item 2, the left call computes the sum of completion times for jobs in (i, s), and the right call the sum of completion times for jobs in (s + j. Then h is oo if a constraint is violated (between a job whose position is between + 1 and j, and a job whose position is between i and s), and 0 otherwise.
Here again, this generalizes to many other single machine scheduling problems (involving other constraints and/or weights on jobs and/or other objective functions like sum of tardiness).
Social welfare maximization in keyword auctions with ex-
'To be more precise, deal with the cases S in the sum it should cost, (Q)()) 1, for t max(i 1).
6

---

Polynomial Time Learning-Augmennted Algorithms for NP-hard Permutation Problems
ternalities is NP-hard (Fotakis et al., 2011; Gatti al., 2018) and is example of c-local permutation problem.
11
ai-k k
0g
aj=k
aj
aj+k
Og
4. Proof of Theorem 1.1
In this section, we present the proof of Theorem 1.1, the main result of this paper. Using Lemma 2.6, what remains to be shown that if problem decomposable or e-local, then it is polynomial time solvable when being (log n)- position enhanced. We provide corresponding DP algo- rithm for decomposition in Lemma 4.1 (which extends the one of (Braverman & Mossel, 2008)) and for c-locality in Lemma 4.2
R
Figure 3. Selecting the set I" involves choosing j - - + 1 ele- ments that include all elements T and are contained within I+ (highlighted in green). This corresponds to selecting 2k elements from the list {ai-x, 0o-=k,,.--..1..... as+k-1, aj-k+1,......... aj+*) of 4k elements. Similarly, selecting 1 requires choosing ments that include lz and are contained within 1 (in bluc). This involves selecting &s elements from the list (ai-ks..., 02+4-13 ( of 2k elements. The same logic applies for I (in red).
elc-
Lemma 4.1. If permutation optimization problem P is decomposable, then its k-position enhanced version solv- able in time O(n 20(k) f) where is the time to compute the value of a solution.
I' (i.j) are fixed, the remaining elements belong to 12()) (see Figure for an illustration). Thus the number of differ- ent guesses we have to do is bounded by 22k+ 26k
This gives a polynomial computation time when Ollogn), n), provided that & poly(n).
Proof. We will use dynamic programming find op- timal solution for the optimization problem P. Let 0" be an (unknown) optimal permutation such that a (i) 5 e clog n for all i.
Now, let us define for any i, the S(i, of sets (i, of size j i + 1 such that I (1, S (' r r (i, We have that (i, E Sii,)).
Moreover, let C(i 1) be the set of sets I (i) of size i - such that 17 (t) C (1) S (1). We have that (i) E C(i-1) 1). Similarly, we define the set R(j + 1) of sets (i)
Let < j be any indices. Let (i, denote the elements in positions between and j in a, i.e.,
of size n j. j.
(i.jj) (a)(() (o(+))) (
We now define the following problem I(i, for each (i(i,)) E S(i, each (i) C(i - 1) and each (2)()) R( + 1) such that j). T2 (i) and ( are pairwise disjoint, find a permutation of of elements in ['(i,) such that:
Moreover, let
(1) (1=(1), 9o(2) ..., (o(11))
be the elements of the left of and
1o((1) - (15) k. (ar()). ar (i.
[ū) = (do()+)) (o(i-2)) an())
the elements on the right of j. By assumption, we have 17 (1) C (1) C 1 (1), (i, S c
o' (i, optimizes the function g given in the decompo- sition property of P.
and I (1) C (20 C (i) where
(1) {a1, 02 11
Based on the decomposition property of g, we will solve the problem via dynamic programming. Note that we find an optimal solution by solving [11, Assume for the sake of simplicity that n is power of two. We will solve I(1, n) using the solutions of Z(1, n/2) and I(n/2 + 1, n). and so on. We solve the leaves of the tree (containing only one element) in constant time, and we have total n subproblems.
(f) (a1, 02 ................................ O ai-k-1) 1),
(1,5) = (ai-k, aj k+l aj+k]:
(1,5) = (aitk, di-ktl kj
(5) {aj+1-k: 0j an)
(5) {aj+1tk, a242th.......................... ).
Let us explain how we solve I(i,j) using the solutions of Z(i, s) and I(s + L,j), where i < S j.
Thus, selecting the sets (1), ji. and (J) involves selecting & elements from a list of 2k elements for IJ, (i) and 2k elements from 4h elements for I (i, Once (i),
Let (i( E S(i.j), [1) E L(i - 1) and Iz(()) e R(j + 1). Thanks to the decomposition property on g
7

---

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
(see Definition 3.1), (), (1) and (2(() being fixed,
There are most 2k choices for (o()), each DP entry can be computed in time O(k). Overall, we have that the running time is O(n 22 ket1).
an optimal o' (i..)) is composed of optimal on [i, 8] and an optimal solution on [s I, 1, There are at most 20(k)
choices to partition ji) into two sets (i, d+ E ((i,
and (s + 1, E (( + 1. So we can compute an opti- mal solution our subproblem using (0 calls to the DP
5. About position-enhanced permutation problems
table (on subproblems in I(i, 8) and I(s + 1,)).
The dynamic programming algorithms of Lemmas 4.1 and 4.2 show that O -poositiion enhanced versions of decomposable or c-local permutation problems are solvable in polynomial time. In this section, we show two comple- mentary results on position-enhanced versions of permuta- tion problems that, though technically quite easy, enlight interesting limitations to Lemma 2.6:
Now we can also prove a similar lemma for the case of a e-local permutation optimization problem, using a different DP.
Lemma 4.2. Let P be c-local permutation problem. Its k-position enhanced version is solvable in time O 22k kett).
First we show that there are some permutation prob- lems which remain hard to solve in polynomial time even when being O(log n -position enhanced.
Proof. We will use again dynamic programming to find optimal solution for problem P. Let i be any index. Let I' (i) denote the elements in an optimal order in positions between 1 and in o, i.e., I (i) (ao(1))..........))))))))))) . (a(t))))..,
Second, we show that this bound O(log n) is tight, meaning that there are decomposable problems and c-local problems which remain hard when being f(n) log n-position enhanced, as soon as f is un- bounded.
By assumption, we have that I (1) (1) C (i), where
r (i) =aa,, a2..........................00.. .......... d I+ {a,, a............................... ...8)
Thus, selecting the set I" (i) involves selecting i elements from list of 2k elements. Therefore, the number of differ- ent guesses we have to do is bounded by 22h
5.1. A log(n) positiio--n--eeeeeeeedd hard problem
Let consider the following problem called Permutation Clique: we given graph G (V, E) on n t² vertices Pi.j. i = 1....,t. The goal is to determine whether there exists permutation a over {l,...,(} O such that the vertices (i,)(()+ = .t. form a clique in G. If one puts vertices in a tabular of size f t, then we want to find clique of vertices with exactly one vertex per row and one per column. This problem is trivially solvable in time 20 t), Interestingly, (Lokshtanoy et al., 2018) showed the following, where ETH stands for Exponential Time Hypothesis:
Let us now define for any i the set S of sets (t) of size such that (1) S (1) S (t). We have that (i) E (1).
Similarly, let (1 + 1,2+ c) denote the elements in positions between i + 1 and i + in σ. Here, we have to select each of these elements among list of 2k + elements, so the number of different guesses is bounded by O(k") (as c is a constant). Moreover, for each guess we also consider all different permutations of the c elements (denoted by a + c)) which takes constant time (as is constant).
Proposition 5.1. (Lokshtanov al., 2018) Under ETH, Permutation Clique is not solvable in time 20(1 logt).
We also define for any the set S(i + 1, + c) of sets I' + 1,i+c) c) of size such that I (i + 1, +c) C +
We show that this problem remains hard even when being O(log posiiioo enhanced. Formally, the problem is de- fined as follows. We are given an instance G (V, E) of Permutation Clique on f2 vertices, and we want to determine if there is permutation a over (1....,(} such that:
C +1 We have that ( (i++,,++)) S(i + 1,1++c)..
Let us now explain how we solve the problem using dynamic programming which is based on the property of c-locality. For every entry of the DP table we have the following:
(1) (a) - S clogt for all i I....,
DP(Ss(1), (o(t)))).... (o(tt))) min (DP(S.(i) (o(i)),aa()) ao(i), ..... (o(Ho)11)
(2) (vro(0) ;i= 1,...,t) O} is a clique in G.
Proposition 5.2. Under ETH,
a(a) (costr(uo(() (o(1t)).....................)... (e(tt))).__(((tt)))
Enhanced Permutation Clique is not solvable in polynomial time (for any e > 0).
8

---

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
Proof. Let us consider an instance G (V, of Permu-
Proposition 5.4. For any unbounded increasing function
tation Clique, on n l² vertices {wi. : i, 1, 1.-..,.}, 1). Let t' = 2//,, We build from G graph G" = (V', E")
J. f(n) log Pos-oooooond--ahaaeeee TSP is not solvable in polynomial time under ETH.
n'= = t2 vertices [e(g i.j = =1,... 1.....t')) .'} where:
Proef. The proof is similar to the one of Proposition 5.3. This time, we add dummy vertices that are all at distance O from given initial vertex v (and all distances between them are 0), so that there are N = 22"f(a) vertices in total. Then we know that there exists an optimal solution in which these vertices are ranked last in the permutation (the solution starts with v), so we get as previously f(N) log N-position enhancement "for free". We get the same conclusion, us- ing the fact that TSP is not solvable in time 20(n) under ETH (Impagliazzo et al., 2001).
For i1, i2, J2 S l: yi adjacent to V if and only Ut..i is adjacent Vi2.j2 in G;
For i,j & t and l v is adjacent to vg
For E,, & ve, adjacent to .22
By construction, a (non trivial) clique in G' is composed by a clique in G plus 'diagonal' vertices we.e- Hence, there is a permutation clique of size in G' if and only if there is a permutation clique of size in G. Moreover, we know by construction that if there is a permutation clique induced by o' in G', then for > t la (f) = l (diagonal vertices), and for L 1 (() < t. Then in any case, (e) El t = clog t',
Similar proofs be easily derived for other problems, such as Min Linear Arrangement and the single-machie sum of completion time problem considered in Section 3.
Suppose that we answer to (clog t') Frositioned-Enhane Permutation Clique in polynomial time On"'). The con- struction of G" takes time (n'), so we can solve Permu- tation Clique in time (n"') Ottc') 20(1), This is in contradiction with ETH.
Acknowledgement
Dimitris Fotakis has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEUU Program. Michalis Xefteris was sup- ported by the framework of H.F.R.I call "Basic research Fi- nancing (Horizontal support of all Sciences)" under the Na- tional Recovery and Resilience Plan "Greece 2.0" funded by the European Union NextGenerationEU I..F...I. Project Number: 15877). Panagiotis Patsilinakos has received sup- port under the program "Investissements d' Avenir" launched by the French Government. PSL JRC 2024 N 2024- 488.
5.2. Hardness results for worse than Ollog rt) postipppoooiinnoaaaaeee tenteccmentn
Let us now go back decomposable and c-local problems, and show that the n -oooiiiooo enhancement neces- sary for some problems.
Proposition 5.3. For any unbounded increasing function f, (n) log Posiitioned Poosiittooone---nhnneeedddd Max Acyclic Subgraph is not solvable in polynomial time under ETH.
Impact Statement
Proof. We make a reduction from Max Acyclic Subgraph, which is not solvable in time 20(n) under ETH (from the linear reduction from vertex cover (Karp, 1972) and the hardness of vertex cover (Impagliazzo al., 2001)). Let G (V, E) be a directed graph. We build graph G" by adding G dummy vertices so that G' has N = 20) vertices. We keep the ares that are in G but do not add any new ares. Then the order in which we put dummy vertices does not change the objective function. So we know that there is an optimal solution such that (1)) = for i > n and (i) S n. for S n, and there a restricted to {L..... n is an optimal solution for G. So we know that (a(1) - il < n f(n) log N < ((N) N.
This paper presents work whose goal is to advance the field of Machine Learning by further exploring its interactions with Theoretical Computer Science. There are many poten- tial societal consequences of our work, none which we feel must be specifically highlighted here.
References
Antoniadis, A., Eliás, M., Polak, A., and Venzin, M. Ap- proximation algorithms for combinatorial optimization with predictions, 2024. arXiv:2411.1666
Athey, S. and Ellison, G. Position Auctions with Consumer Search. The Quarterly Journal of Economics, 126(3): 1270, 08 2011.
Now, suppose that we can solve f(n) log n-Pootiionee- Enhanced Max Acyclic Subgraph in polynomial time O(N)). Then we would solve Max Acyelic Subgraph in time ((2)m/((m) = 20(n) as f is unbounded. This is im- possible under ETH.
Bampis, E., Escoffier, B., and Xefteris, M. Parsimonious learning-augmentee approximations for dense instances

---

Polynomial Time Learning-Augmentedd Algorithms for NP-hard Permutation Problems
of A'Phaad problems. In Proc. 41st Int. Conf. Machine Learning (ICML), volume 235, pp. 2700-2714, 2024.
Ergun, J. C., Feng, Z., Silwal, S., Woodruff, D., and Zhou, S. dearning-augmentn k-means clustering. In Proc. 10th Int. Conf. Learning Representations (ICLR), 2022.
Bengio, Y., Lodi, A., and Prouvost, A. Machine learning for combinatorial optimization: A methodological tour d'horizon. Eur. J. Oper. Res., 290(2):405-421, 2021.
Fotakis, D., Krysta, P., and Telelis, O. Externalities among advertisers in sponsored search. Proc. 4th Int. Symp. on Algorithmic Game Theory (SAGT), volume 6982, pp. 105-116, 2011.
Braverman, M. and Mossel, Noisy sorting without resam- pling. In Proc. 19th Symp. Discret, Algorithms (SODA), pp. 268-2688822 276, 2008.
Gamlath, B., Lattanzi, S.,, Norouzi-Fard, A., and Svensson, O. Approximate cluster recovery from noisy labels. In Proc. 35th Conf. on Learning Theory (COLT), 2022.
Braverman, M. and Mossel, E. Sorting from noisy informa- tion, 2009, arXiv:0910.1191.
Garey, M. R. and Johnson, D.S. Computers and Intractabil- ity: Guide to the Theory of NP- VVP-Completeness. W. H. Freeman, 1979. ISBN 0-7167-1044-7.
Braverman, V., Dharangutte, P., Shah, V., and Wang, C. Learning-Augmentt Maximum Independent Set. In Approx., Random., and Comb. Optim. Algorithms and Techniques (APPROX/RANDMM) volume 317, pp. 24:1- 24:18, 2024.
Gatti, N., Rocco, M., Serafino, P., and Ventre, C. Towards better models of externalities in sponsored search auc- tions. Theoretical Computer Science, 745:150-162, 2018.
Busa-Fekete, R., Fotakis, D., Szörényi, B., and Zampetakis, M. Optimal learning of mallows block model. In Con- ference on Learning Theory, COLT 2019, volume 99 of Proceedings of Machine Learning Research, pp. 529-532.
Ghoshal, S., Makarychev, K., and Makarychev, Y. Constraint satisfaction problems with advice, 2024. arXiv:240.00221..
PMLR, 2019.
Im, S., Kumar, R., Petety, A., and Purohit, M. Parsimonious leamiig-auggmented caching. In Proc. 39th Int. Conf. Machine Learning (ICML), volume 162, pp. 9588-9601, 2022.
Cappart, Q., Chételat, D.,, Khalil, E. B., Lodi, A., Morris, C., and Velickovic, P. Combinatorial optimization and reasoning with graph neural networks. J. Mach. Learn. Res., 14:100:1-130:1, 2023.
Impagliazzo, R., Paturi, R., and Zane, F. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 6344)51 2001.
Chen, J. Y., Silwal, S., Vakilian, A., and Zhang, Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, ICML 2022, volume 162 of Proceedings of Machine Learning Research, pp. 3582-3602. PMLR, 2022.
Karp, R. Reducibility among combinatorial problems. In Complexity of Computer Computations, pp. 85-103. Plenum Press, 1972.
Cohen-Addad, V., d'Orsi, T., Gupta, A., Lee, E., and Pani- grahi, D. for maximum cut and related problems. In Proc. 38th Adv. Neural Inf. Processing Syst. (NeurIPS), volume 37, pp. 15961-25980 2024.
Khalil, E. B., Dai, H., Zhang, Y., Dilkina, B., and Song, L. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, pp. 6348-6358, 2017.
approximation algorithms
Dinitz, M., Im, S., Lavastida, T., Moseley, B., and Vassilvit- skii, S. Faster matchings via learned duals. In Proc. 35th Adv. Neural Inf. Processing Syst. (NeurIPS), 2021.
Lawler, Sequencing jobs to minimize total weighted completion time subject precedence constraints. Ann. Discrete Math., 2:75-90, 1978.
Dong, Y., Peng, P., and Vakilian, A. Learning-o Augmented Streaming Algorithms for Approximating MAX-CUT. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325, pp. 44:1-44:24, 2025.
Lindermayr, A. and Megow, N. ALPS. https: tittt i
/ //al //algoria io/
ct at ions,,, .ot.oionnss.b......
Lokshtanov, D., Marx, D.,, and Saurabh, S. Slightly super- exponential parameterized problems. SIAM J. Comput., 47(3):675-702, 2018.
Edelman, B., Ostrovsky, M., and Schwarz, M. Internet Advertising and the Generalized Pecond-Priie Auction: Selling Billions of Dollars Worth of Keywords. American Economic Review, 97(1):242- -229, March 2007.
Lykouris, T. and Vassilvitskii, S. Competitive caching with machine learned advice. ACM, 68(4), 2021.
10

---

Polynomial Time Learning-Augmenteed Algorithms for NP-hard Permutation Problems
Mahdian, M., Nazerzadeh, H., and Saberi, A. Allocating online advertisement space with unreliable estimates. In Proc. 8th ACM Conf. on Electronic Commerce (EC), pp. New York, NY, USA, 2007.
Nguyen, D., Chaturvedi, A., and Nguyen, H. Im- proved Garning-augmentin algorithms for k-means and k-medians clustering. In Proc. 11th Int. Conf. Learning Representations (ICLR), 2023.
Sakaue, S. and Oki, T. piscrete-covvex-analsi--------s- framework for warm-starting algorithms with predictions. In Proc. 36th Adv. Neural Inf. Processing Syst. (NeurIPS), 2022.
Varian, H. R. Position auctions. International Journal of Industrial Organization, 1566)11663- 2007.


Reviews:
[{"review_id": "d0oqR3htXr", "reviewer": "Reviewer_PUBJ", "summary": "This paper studies a broad class of optimization problems that can be captured via permutations with the help of predictions. For example consider the TSP problem: the optimal solution corresponds to a permutation of the input points. The predictions are weather point i precedes point j in the permutation and each pair of information is correct with probability 1/2 + eps iid (note one cannot re-query the same pair). In generally, the authors note that many classic optimization problems can fit this framework.\n\nAt a high level, the idea is to draw connection to a prior studied problem of sorting with such similar noisy information. Using ideas from a series of papers from Braverman and Mossel, the submission at a high level, first reconstructs a permutation that matches the information given by the prediction. There is a key property that every point won't be 'too far away' (within O(log n)) of its true position in the reconstructed permutation. If the optimization problem has the special structure that one can ignore such far away interactions (the authors identify many such examples), one can then optimally fix the local mistakes by using dynamic programming to get an overall polynomial time. Another nice aspect is that the total number of queries made to the oracle is bounded by O(n log n) but this seems to follow from the Braverman Mossel results.\n\nIn summary, I am quite positive of the paper for the following reasons:\n\nThere are several aspects of this paper that I enjoy:\n- Studies NP hard optimization problems: this seems like a promising area for learning augmented algorithms (and was the main motivation of this paper following some nice work on max cut)\n- Introduces a general framework by looking at problems that can be represented as permutations.\n- The algorithms are very simple and intuitive\n\nHowever, here are some cons:\n- Since the algorithms are quite simple, i find the lack of experiments to be a bit disappointing since i think they could work very well. \n- The question of where the predictions are coming from (just the motivations even)  is not really discussed\n- I could not easily separate the technical contributions made by the paper and the works of Braverman and Mossel. I recommend better highlighting what arguments are novel to the submission. However, I view a major part of the submission as a conceptual contribution so this point is somewhat minor to me.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and the provided questions. \n\n- (Comment) Minor comment but [1] is also among the first paper to use predictions to warm start ...\n\n(A) Thank you, we will add this reference on a revised version.\n\n- (Comment) I was really confused in the beginning where the dependence on epsilon goes to. For example, if epsilon = 0 then the advice is useless. [...] \n\n(A) Indeed, this is also pointed by another reviewer, we will make the dependency on epsilon more explicit in a revised version.\n\n- (Question) What if you are given a 'noisy' ranking in the beginning? This has some pros and cons: pros is the information is only O~(n) bits rather than n^2 (but harder to incorporate 1/2 + eps criteria).\n\n(A) First, we underline that our approach also uses O(n log n) bits of predicted information. If we understand correctly, the question is \"what happens if we have predictions queries relative to a noisy ranking sigma' (sigma' being noisy wrt to the true optimal ranking sigma^*)?\". \n\nIt depends of course on the noise. An easy case is when |sigma'(i)-sigma^*(i)|=O(log n) for all i (whp), as then the results are still valid since we still have k-enhanced problems with k=O(log n). If this 'pointwise' bound does not occur, it is not clear whether weaker assumptions on the noise could be sufficient. \n\nAn interesting case where this bound occurs is when the prediction is a noisy permutation sampled from a Mallows distribution [1]. A Mallows distribution is defined w.r.t. the optimal permutation $\\pi^*$ and a noise parameter $\\beta \\in [0, 1]$. Then, the probability of generating a permutation $\\sigma$ is proportional to $e^{- \\beta d_{KT}(\\sigma, \\pi^\\ast)}$, where $d_{KT}(\\sigma, \\pi^\\ast)$ is the Kendal tau distance between $\\pi^*$ and $\\sigma$ (the Kendal tau distance accounts for the number of pairwise disagreements between $\\pi^*$ and $\\sigma$). The case where $\\beta = 0$ corresponds to the uniform distribution, while the case where $\\beta \\leftarrow \\infty$ allocates probability $1$ to $\\pi^\\ast$. This case was also studied in the follow-up paper by Braverman and Mossel [1]. It can be shown (e.g., [1, Lemma 17]) that for any constant $\\beta > 0$, $|\\sigma(i)-\\pi^*(i)| = O(\\log n)$ for all $i$ (whp). Therefore, our results can be extended to the case where the prediction is provided in the form of a noisy ranking sampled from a Mallows distribution with the optimal permutation as $\\pi^\\ast$ and a constant noise parameter $\\beta > 0$ (here $\\beta$ plays the role of $\\epsilon$ and our running time has $\\mathrm{poly(1/\\beta)}$ in the exponent).\n\n[1] Braverman, M. and Mossel, E. Sorting from noisy information, 2009. arXiv:0910.1191.\n\n[2] C. L. Mallows. Non-null ranking models. Biometrika, 44:114–130, 1957.\n\n- (Question) Are there lower bounds stating that Omega(n log n) queries are necessary?\n\n(A) Actually $\\Omega(n \\log n)$ queries are necessary even in the case of perfect predictions. Indeed, when answers to queries are correct (with probability 1) the Noisy Sorting Without Resampling problem becomes sorting by comparisons (where comparisons are queries). It is well known that sorting by comparisons needs $\\Omega(n \\log n)$ comparisons (even for randomized algorithms), so even in the case of 'perfect predictions' (correct comparisons)  $\\Omega(n \\log n)$ queries are necessary to sort/recover the order.\n\nThanks for pointing this, we will add this remark on a revised version.\n\n- (Question and Comment) Can the authors comment on how easy the ranking permutations would be learn / initialize in practice? The question of where the predictions are coming from (just the motivations even) is not really discussed.\n\n(A) This point is also raised by reviewer bUbX. Please read our answer in the rebuttal of reviewer bUbX (first point (comment) in that rebuttal), thanks.", "claims_and_evidence": "Yes all claims seem sound.", "methods_and_evaluation_criteria": "No empirical evaluation.", "theoretical_claims": "I checked some theoretical proofs and they seem sound.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper extend a new direction in learning-augmented algorithms which studies NP hard problems by introducing a framework for solving problems related to permutations.", "essential_references_not_discussed": "Minor comment but [1] is also among the first paper to use predictions to warm start and optimization problem and then solve the initialized problem optimally. \n\n[1] Faster Fundamental Graph Algorithms via Learned Predictions. ICML 22", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "A minor point: I was really confused in the beginning where the dependence on epsilon goes to. For example, if epsilon = 0 then the advice is useless. Only after a few passes did I understand that the running time blows up (so the running time is polynomial for any fixed epsilon). This makes sense but the authors should highlight this a bit more.", "questions_for_authors": "- What if you are given a 'noisy' ranking in the beginning? This has some pros and cons: pros is the information is only O~(n) bits rather than n^2 (but harder to incorporate 1/2 + eps criteria).\n- Are there lower bounds stating that Omega(n log n) queries are necessary? \n- Can the authors comment on how easy the ranking permutations would be learn / initialize in practice?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ipL19dyCbA", "reviewer": "Reviewer_bUbX", "summary": "The paper studies how to tackle NP-hard permutation problems with the help of predictions on the relative position of any two elements with respect to some fixed unknown optimal permutation. Each query is independently correct with probability at least $1/2 + \\varepsilon$ for some unknown $\\varepsilon$. Building upon a prior result [BM08] that the \"most consistent\" permutation with respect to these faulty predictions is O(log n)-\"close\" to the fixed unknown optimal permutation, the authors propose two sufficient conditions (decomposition and c-locality) under which a \"close\" permutation can be used as a warm-start to optimally solve the NP-hard problem in polynomial time using dynamic programming methods. The authors further prove hardness results that their results for decomposition and c-locality are tight, and that having a \"close\" permutation does not always suffice in general.\n\n[BM08] Braverman, M. and Mossel, E. Noisy sorting without resampling. In Proc. 19th Symp. Discret. Algorithms (SODA), pp. 268–276, 2008.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and the provided questions. We will implement the suggestions on a revised version.\n\n- (Comment) While theoretically interesting, it is unclear to me how such a prediction can be available in practice for each of the problems mentioned in the paper [BM08]\n\n(A) This point is also raised by Reviewer PUBJ (\"Can the authors comment on how easy the ranking permutations would be learn / initialize in practice? The question of where the predictions are coming from (just the motivations even) is not really discussed.\"). We provide here a common answer to these points about the predictions.\n\nOur framework and results indeed ask for good predictions of optimal solutions for hard optimization problems. This is clearly a strong assumption. The soundness bound of $1/2+\\epsilon$ is actually not very strong (in the sense that any $\\epsilon>0$ works), but the independency might be harder to get in practice. We do not claim that there are currently ML algorithms on the shelf that have the required accuracy.  However, we stress the fact that a large number of recent works do focus on getting predictions for discrete optimization problems. This area, part of the larger question of using ML for optimization, is still in its early stage of development but is growing very fast. We refer to [1,2] for survey-like papers with many references in it. We also quote a specific work on predictions for problems including (Euclidean) TSP [3]. Hence, we believe that the quick development of the field makes it reasonable to hope for some accurate predictors for some permutation problems  in the near future, making our framework possibly relevant also from a more practical viewpoint. Also, we think that the theoretical result we give on the potential fruitful use of good predictions in solving hard permutation problems might be a further motivation for studying, in ML, predictions for solutions of optimization problems.\n\n\nNevertheless, there are restricted settings where one could outline how such noisy predictions of the optimal permutation can be learned. E.g., consider a setting where instances are stationary and instance stationarity implies that the optimal solution / permutation of each instance is a noisy sample from a Mallows distribution $\\mathcal{M}(\\pi^\\ast, \\beta)$ with $\\pi^\\ast$ corresponding to the optimal permutation of the \"mean\" instance and the noise parameter $\\beta$ accounts for the variance of the instance distribution (for a more concrete example, we may think of a Euclidean TSP setting where the location of each vertex $v_i$ is drawn from a fixed distribution $\\mathcal{V}_i$ and the distributions $\\mathcal{V}_1, \\mathcal{V}_2, \\ldots, \\mathcal{V}_n$ are mutually independent). Such a Mallows distribution $\\mathcal{M}(\\pi^\\ast, \\beta)$ can be learned [4] up to KL distance $\\epsilon$ from the optimal (or near-optimal) solutions of $O(\\frac{\\ln(1/\\delta)}{n \\epsilon^2 } + \\frac{\\ln(n / \\delta)}{\\beta})$ instances sampled independently from the instance distribution (where $n$ is the number of vertices and $\\delta$ is the probability that the learning algorithm fails). Samples from $\\mathcal{M}(\\pi^\\ast, \\beta)$ can be used as predictions (in the form of noisy rankings, as discussed in the response to Reviewer PUBJ) in our approach. \n\n[1] Y. Bengio, A. Lodi, A. Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. EJOR 290, Issue 2, 16 April 2021, Pages 405-421\n\n[2] Q. Cappart, D. Chételat, E. B. Khalil, A. Lodi, C. Morris, P. Velickovic. Combinatorial Optimization and Reasoning with Graph Neural Networks. J. Mach. Learn. Res. 24: 130:1-130:61 (2023)\n\n[3] E. B. Khalil, H. Dai, Y. Zhang, B. Dilkina, L. Song: Learning Combinatorial Optimization Algorithms over Graphs. NIPS 2017: 6348-6358\n\n[4] R. Busa-Fekete, D. Fotakis, B. Szörényi, M. Zampetakis. Optimal Learning of Mallows Block Model. COLT 2019: 529-532.\n\n- (Question) Technically speaking, needs to be constant otherwise the running time $n^{O(1/\\epsilon^4)}$ is not polynomial, right? \n\n(A) Indeed, this is needed for the running time to be polynomial. We will make this explicit.\n\n- (Question) For completeness of the problem modeling, please provide references for NP-hardness of minimum linear arrangement and TSP.\n\n(A) Indeed, we will do this.\n\n- (Question) In Lemma 4.1, what is the purpose of introducing $n^d$? $d$ was never mentioned in the proof and we actually need to be constant otherwise , right? How about changing the statement to $O(n.2^{O(k)}t)$ where $t$ is the time to compute the value of a solution? Also, [...] being mentioned at all.\n\n(A) Indeed, this reformulation $O(n.2^{O(k)}t)$ is correct and simpler, we will make the modification. The dependency on the time to compute the value of the solution arises when selecting the best partition of $I'(i,j)$ into two sets among $2^{O(k)}$ possible choices. We will add a remark about this in the proof.", "claims_and_evidence": "Yes, proofs were given.", "methods_and_evaluation_criteria": "Method is sound.", "theoretical_claims": "I checked the proofs. Looks correct.", "experimental_designs_or_analyses": "No experiments as it is a theoretical paper.", "relation_to_broader_scientific_literature": "The work here contributes to the field of learning-augmented algorithms in the form of speeding up solving of NP-hard problems in the presence of noisy predictors. More precisely, the authors provide two very general conditions (decomposability and c-locality) which extends the applicability of [BM08].\n\n[BM08] Braverman, M. and Mossel, E. Noisy sorting without resampling. In Proc. 19th Symp. Discret. Algorithms (SODA), pp. 268–276, 2008.", "essential_references_not_discussed": "Not that I am aware of", "other_strengths_and_weaknesses": "# Strengths\n- The authors provide two very general conditions which extends the applicability of [BM08]\n- Hardness results are given to show the tightness of their results\n- The paper is very well-written in general; the exposition and proofs are very easy to follow\n# Weaknesses\n- While theoretically interesting, it is unclear to me how such a prediction can be available in practice for each of the problems mentioned in the paper\n\n[BM08] Braverman, M. and Mossel, E. Noisy sorting without resampling. In Proc. 19th Symp. Discret. Algorithms (SODA), pp. 268–276, 2008.", "other_comments_or_suggestions": "- Suggestion: Mention that the predictions are with respect to some unknown fixed optimal solution in the abstract? My initial reading of the abstract immediately raised questions in my head about globally inconsistent predictions but was only resolved when I read Line 62.\n- Typo: Is there an extra space before the full stop at the end of Theorem 1.1?\n- Suggestion: There were a few places where $\\pi^*$ was described as \"optimal solution\" instead of \"s-optimal solution\". Maybe add in \"s-\" so that it avoids confusion with the underlying unknown optimal permutation $\\sigma^*$?\n- Paraphrase suggestion for the first sentence paragraph before Section 3: \"Motivated by Lemma 2.6, we give two sufficient conditions ..., for k = O(log n), in the next section.\" I personally found the phrasing \"Then, we mainly exhibit...\" a bit awkward / does not flow well into the next section, but this is just a minor rephrasing suggestion that you may choose to ignore.\n- Typo: In Definition 3.1, I believe the $S(\\cdot)$ should be $S_{\\sigma}(\\cdot)$? There are such instances $S(\\cdot)$ in the rest of this document. Also, is $\\mathcal{S}$ in the proof of Lemma 4.1 the same thing as $S_{\\sigma}(\\cdot)$? Maybe do a ctrl-F on \"S(\" and \"\\mathcal{S}(\" and check?\n- Typo: Inconsistent bracketing on the last sentence of proof in Lemma 4.1\n- Right side of Line 371 in the proof of Lemma 4.2: \"i+1, i+c in $\\sigma$\" should be \"i+1 and i+c in $\\sigma$\".", "questions_for_authors": "- Question: Technically speaking, $\\varepsilon$ needs to be constant otherwise the running time $n^{O(-\\varepsilon^4)}$ is not polynomial, right? I can't remember if \"constant $\\varepsilon$\" was mentioned somewhere in the paper.\n- For completeness of the problem modeling, please provide references for NP-hardness of minimum linear arrangement and TSP.\n- In Lemma 4.1, what is the purpose of introducing $n^d$? $d$ was never mentioned in the proof and we actually need $d$ to be constant otherwise $n^d \\not\\in poly(n)$, right? How about changing the statement to $O(n \\cdot 2^{O(k)} \\cdot t)$ where $t \\in poly(n)$ is the time to compute the value of a solution? Also, please mention where the dependency on this computation time shows up in the proof. Currently it is not being mentioned at all.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NIL"}}, {"review_id": "DkMeQxbGut", "reviewer": "Reviewer_YZRG", "summary": "The paper presents a framework for studying NP hard optimization problems in the framework of learning-augmented algorithms. Specifically, the authors consider a class of permutation problems, where a solution is determined by a total order of a set of $n$ items, such as TSP, single machine scheduling, etc, and that satisfy certain properties such a c-locailty or decomposition. An algorithm has access to a noisy (consistent) oracle that outputs for two elements $u,v$ whether $u$ comes before $v$ in a fixed optimal solution with probability of at least $\\frac{1}{2}+\\varepsilon$ with $\\varepsilon > 0$. \n\nThey present a polynomial-time algorithm for this class of permutation problems that outputs an optimal solution with high probability. Moreover, their algorithm only uses $O(n \\log n)$ queries to the noisy oracle, hence can be considered to be parsimonious. Finally, they show that many well-known NP-hard permutation problems lie in this class, and present tightness of their bounds and also of their approach.\n\nTheir approach builds up on a beautiful result by Braverman & Mossel, who considered the problem of sorting using a noisy oracle without resampling. On a high-level, they first use this result to compute a permutation $\\pi^*$ that minimizes the total number of inversions compared to the oracle. Then they use a property proven by Braverman & Mossel that such a permutation is \"close\" to an optimal solution. They show the c-locality properties or the decomposition properties suffice to compute the optimal solution in polynomial time given $\\pi^*$ .", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback.\n\nAbout the comments of the reviewer: The model of epsilon-accurate predictions has indeed been used for other problems. So, the model is not novel, but we would like to note that our work is completely different from previous works on this model both on the techniques used, on the obtained results (polytime exact algorithms and not approximation algorithms as previously studied) and on the problems tackled (permutation problems).", "claims_and_evidence": "All claims are proven formally.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I checked a few arguments in Section 3 and the proof in Section 4.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper falls in a line within the area of learning-augmented algorithms that studies the power of predictions for classic questions in complexity theory. The model there an algorithm receives a \"correct\" signal with probability strictly larger than 1/2 has previously been successfully applied to break the hardness of other problems with high probability.\n\nThe paper also relates their algorithm to the idea of \"warm starting\" algorithm, a technique that previously has been used for improving the runtime with predictions.", "essential_references_not_discussed": "As far as I see, all relevant references are there.", "other_strengths_and_weaknesses": "Strengths\n- The result is interesting and increases our understanding on $\\varepsilon$-accurate predictions.\n- The approach reuses previous results, and thus, is quite simple and easy to present and hence understandable\n- The result captures many different problems by definition an appropriate subclass of permutation problems.\n\nWeaknesses\n- The model of $\\varepsilon$-accurate predictions has previously been used for other problems. Thus, one can argue that the present paper only uses known techniques.\n- The results heavily depends on the result of Braverman & Mossel and thus slightly lacks technical novelty. Given that this is an ML conference, I would not weigh this point too much.\n\nIn summary, I believe that this is a neat and approachable result that contributes well to the field of algorithms with predictions.", "other_comments_or_suggestions": "I find the definition of $s$-optimal a bit confusing, as it seems that the $s$ will be user interchangeably, which however does not happen in the paper. Thus, I would suggest to use a different term for this property.", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o8ggbU0pFN", "reviewer": "Reviewer_aLF5", "summary": "The paper considered permutation-based NP-hard problems with learning-augmented oracles. The paper proposed a novel framework that given a learning-augmented oracle on the ordering of pairs with correct probability $½+\\Omega(1)$, solves certain families of NP-hard problems exactly in polynomial time and O(n log n) queries to the oracle predictions. The families of problems should satisfy either the ‘decomposable’ property, which means the ordering outside a subproblem does not matter for the subproblem itself, or the ‘locality’ property, which means the objective on a local permutation index is only dependent on the c neighboring indices. The paper provided an analysis (theorem 1.1) for the performance guarantees based on sorting without resampling results in BM [SODA’08]. The paper then studied a handle of example problems, including problems that satisfy the decomposable properties, e.g., maximum acyclic subgraph and minimum linear agreement, and the problems with the locality property, e.g. the traveling salesperson problem.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and the provided questions.\n\n(Question/Comment) \"A broader discussion about learning-related algorithms would be better (e.g., learning augmented frequency estimation, e.g., Aamand et al. [NeurIPS’23]; TSP problem, e.g., Chawla and Christou [APPROX’24]) [...]\"\n\n(A) We thank the reviewer for this suggestion, we will provide a broader discussion about learning-augmented algorithms and add the references in the article.\n\nWe note that Chawla and Christou [APPROX’24] do study a variant of TSP but in a very different model: they consider an online problem where the predictions are on the requests that will occur (prediction on locations and time Windows). On the other hand, Aamand et al.[NeurIPS’23] give algorithms with and without predictions that estimate frequencies of elements appearing in a data stream.   \n\n(Q/C) About other graph problems that could be fit into our framework. \n\n(A) In the paper we mention Max Acyclic Subgraph, Min Linear Arrangement and TSP. The result for TSP easily generalizes to similar problems where the objective function is a sum on distances between adjacent vertices in the permutation (such as Hamiltonian Path, asymmetric cases, or even TSP with precedence constraints by incorporating these constraints in the DP). \nWe provide here two other examples of NP-hard graph problems that can be handled in our Framework up to a slight adaptation:\n\n- Minimum traveling repairman, where given an edge-weighted graph we want to find a permutation $(\\pi(1),...,\\pi(n))$ of vertices which minimizes $\\sum_{i>1} d_{\\pi}(\\pi(1),\\pi(i))$ where $d_{\\pi}(\\pi(1),\\pi(i))=\\sum_{j=1}^{i-1}d(\\pi(j),\\pi(j+1))$ is the distance traveled by the traveller in the permutation from the first vertex $\\pi(1)$ to vertex $\\pi(i)$. Stated like this, it is not $c$-local (as it involves distances in the permutation from the initial vertex). However, this function also writes $\\sum_{i\\geq 1} (n-i)d(\\pi(i),\\pi(i+1))$. Then we can apply the same algorithm as we do for 1-local problems. \n\n- Min Cut Linear arrangement, where given a graph we want to find a permutation on vertices which minimizes $\\max_{q=1,...,n} f_{\\pi}(q)$, where $f_{\\pi}(q)=| ( u,v ) \\in E: \\pi^{-1}(u)<q<\\pi^{-1}(v)|$ counts the number of edges \"cut\" at integer point $q$. The objective function to be minimized is a max, not a sum. However, we can still apply our framework with a slight generalization of the definition of decomposition (basically, we need a max instead of a plus, with the condition that there is an optimal permutation on $[i,j]$ that is made of optimal subpermutations on $[i,s]$ and $[s+1,j]$, which is the case here).   \n\n\n(Q/C) \"the paper discussed some recent work on learning-motivated graph algorithms (e.g., CDGLP [NeurIPS’24]; BDSW [APPROX’24]); however, I believe none of these problems (max-cut, MIS, etc.) could be solved with the framework proposed by the paper.\" \n\n(A) Indeed, the point is that problems like Max Cut or MIS are not permutation problems, so they do not fall into our framework. Let us make a remark though. Suppose that for a problem like Min Bisection (or Max Cut) we ask for a permutation, having in mind that the first $n/2$ elements are on one part of the bisection and the last $n/2$ are on the other part. Then our framework easily applies, and we can solve these problems in polytime ... provided that we have the required oracle on queries. But the point is that the queries are not natural for these problems (asking whether $v$ is before $u$ or not in the \"permutation\"); moreover the answers cannot be deduced from the natural queries \"is $u$ on the left or on the right part of the bisection\" (we would not get independent answers).", "claims_and_evidence": "Yes. All theoretical claims are supported by proofs.", "methods_and_evaluation_criteria": "N/A. This paper does not contain experiments.", "theoretical_claims": "On a high level, the main theorem of the paper follows from a ‘positional’ property in the algorithm of BM [SODA’08]. In particular, let $\\pi^*$ be the permutation that maximizes the total number of queries consistent with the oracle and $\\sigma^*$ be the optimal permutation. The algorithm of BM [SODA’08] satisfies the property that for each element $i\\in [n]$, the distance between $\\pi^*(i)$ and $\\sigma^*(i)$ is at most $O(\\log{n})$. Therefore, for each element on $\\sigma^*(i)$, we could enumerate all possible $2^{O(\\log{n})}$ ways to select locally from $\\pi^*$ based on the decomposable or locality properties. This leads to the proof of Theorem 1.1.\n\nI also checked the proofs for the maximum acyclic subgraphs, the minimum linear arrangement, and the TSP problems. These proofs look good as far as I could see.", "experimental_designs_or_analyses": "N/A. Theoretical paper, no experiments are included.", "relation_to_broader_scientific_literature": "The paper explored polynomial time algorithms for NP-hard problems with learning-augmented oracles. This area is important for beyond-worst-case algorithms and complexity.", "essential_references_not_discussed": "For related work, the paper mostly only discussed clustering and graph algorithms in the context of learning-augmented algorithms. A broader discussion about learning-related algorithms would be better (e.g., learning augmented frequency estimation, e.g., Aamand et al. [NeurIPS’23]; TSP problem, e.g., Chawla and Christou [APPROX’24]), especially given that some of these problems are closer to the permutation-based problems studied in this paper. This however is not a dealbreaker type of issue.", "other_strengths_and_weaknesses": "I have a mixed feeling about the paper. On the one hand, I like the idea of using only a sublinear number of predictions to obtain exact solutions for NP-hard problems in polynomial time. On the other hand, I think the properties of decomposable and locality are still restrictive. In particular, to motivate the study of NP-hard problems with predictions, the paper discussed some recent work on learning-motivated graph algorithms (e.g., CDGLP [NeurIPS’24]; BDSW [APPROX’24]); however, I believe none of these problems (max-cut, MIS, etc.) could be solved with the framework proposed by the paper. \n\nThe presentation of the paper also has much to be desired. The high-level description of the decomposable property is a bit too informal, and for a moment, I thought the framework could solve problems like max-cut as well (you can denote the cut as a permutation and find the actual cut from the permutation with $n$ extra time). It turned out that the property actually requires the overall problem to have local invariant properties as required by dynamic programming: this is not clear from the description. Also, I think the notation $\\sigma(i)$ is overloaded between Definition 2.1 and Theorem 2.5. I believe for most places, when you write $\\sigma(i)$, you mean the $i$-th element in the permutation $\\sigma$. However, this is very confusing since it could also mean the permutation index of element $i\\in [n]$. If I’m not mistaken, BM [SODA’08] used the notation in the latter sense.", "other_comments_or_suggestions": "See my comments on 'strengths and weaknesses'.", "questions_for_authors": "Most of the questions are mentioned in my criticism. One additional question: do you see more NP-hard graph problems that could be solved with your framework? This might help improve connections with your motivation.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces a framework for applying learning-augmented algorithms to NP-hard permutation problems such as TSP and single-machine scheduling, where solutions rely on item orderings, and explores how algorithms can leverage a noisy but consistent oracle to guide decisions under structural properties.

It seems many of the same concerns are shared across reviewers regarding:
- the specific technical contributions of the paper beyond the observation of applying the Braverman-Mossel results
- discussion of the motivation or ability to acquire predictions in the suggested oracle model

Additionally, though the paper studies NP-hard problems with advice, it is not clear that these NP-hard problems are unified and central to ML audiences. Although the initial review scores are positive, subsequent reviewer discussion did not reach a resolution on these issues, reflecting a more borderline decision.
Decision: Accept (poster)