Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems

We thank the reviewer for the comments and the constructive encouragement.

We thank the reviewer for the comments and the constructive feedback.

• Is the precision parameter of the predictions epsilon known to the algorithm?

The parameter $\varepsilon$ does not need to be known: for example, we can run our algorithm for each $\varepsilon$ that’s a power of $\frac{1}{2}$ (between $\frac{1}{n}$ and $1$), and return the best of these solutions. One of these will be the right choice of $\varepsilon$, and our analysis holds for that choice of $\varepsilon$. (We will clarify this in the next version of the paper.)

• Many works, especially for online problems, consider predictions whose error is distributed adversarially. Do you think such predictions are also applicable to MAX-CUT and CSPs?

In general, giving the adversary power to choose the vertices it gives correct information on can make the predictions useless. For example, consider an instance containing $(1-\delta)n$ isolated vertices, and an arbitrary “hard” graph on the remaining $\delta n$ vertices. Now the adversary may only provide correct predictions on those isolated vertices.

So, we need to make some assumptions to avoid these pathologies. For example, if we assume that the graph is regular, our Theorem 4.1 for partial predictions that gives $0.858 + \Omega(\epsilon)$ approximation goes through even with deterministic predictions. A similar result holds in general graphs for deterministic predictions satisfying other properties. E.g., if an $\epsilon$ fraction of neighbors’ labels are revealed for every vertex, or more generally, if an $\epsilon$ fraction of edges are incident to the vertices whose labels are revealed. We will include a discussion about deterministic predictions in the Closing Remarks. We hope that our work will spur future investigation into such prediction models.

Thanks for the comments and constructive encouragement.

• For the noisy prediction model of Max Cut, a natural algorithm that comes to mind is to return the better of the GW cut and the predicted cut. Is there an example where this algorithm does not do better than $\alpha_{GW}$?

Yes: consider the tight instances for GW rounding (ones that achieve $\alpha_{GW}$ times the max-cut): such instances were given by Alon, Sudakov, and Zwick, and have maximum cuts that cut about 84.5% of the edges. Given any graph, the predicted labeling cuts each edge in the max-cut with probability $\frac{1}{2} + 2 \varepsilon^2$ and every other edge with probability $\frac{1}{2} - 2 \varepsilon^2$, thereby cutting a bit more than half the edges of the graph for small $\varepsilon$. So on the tight instance graphs, GW rounding would give an $\alpha_{GW}$ approximation (by design), and the predicted cut would give $\approx 0.5/(0.845) \ll \alpha_{GW}$ approximation.

• In the literature on algorithms with predictions, one common way people have modeled the "prediction" is as a single predicted solution, instead of assuming it is generated from a distribution.[..] What are your thoughts on this way of viewing the prediction in the context of your problem?

Such a model would certainly make sense, but the qualitative bounds would depend on the instances. In particular, without additional assumptions, giving the adversary power to choose the partition can make the predictions useless despite being correct on almost all the vertices. For example, consider an instance containing $(1-\delta)n$ isolated vertices, and an arbitrary “hard” graph on the remaining $\delta n$ vertices. Now the adversary may only provide correct predictions on those isolated vertices.

So, we need to make some assumptions to avoid these pathologies. For example, if we assume that the graph is regular, our Theorem 4.1 for partial predictions that gives $0.858 + \Omega(\epsilon)$ approximation goes through even with deterministic predictions. A similar result holds in general graphs for deterministic predictions satisfying other properties. E.g., if an $\epsilon$ fraction of neighbors’ labels are revealed for every vertex, or more generally, if an $\epsilon$ fraction of edges are incident to the vertices whose labels are revealed. We will include a discussion about deterministic predictions in the Closing Remarks. We hope that our work will spur future investigation into such prediction models.

• As 𝜖→1/2 in the noisy predictions model, the prediction approaches the optimal solution, and so the approximation ratio of the algorithm should intuitively go to 1. Is this the case for the algorithm considered in this paper? […]

Our algorithms indeed achieve a near-perfect approximation as the advice becomes nearly perfect. For the noisy model, when $\epsilon=1/2 - \delta$ for small $\delta>0$, it can be shown that a simplification of our algorithm in Section 3.1 guarantees an $(1-O(\sqrt(\delta)))$-approximation. The simplification is just ignoring $\Delta$ and $\eta$, wideness and prefixes, and letting $\tilde{A} = A$. Then Lemma 3.5 can be shown to hold with the the right hand side replaced by $O(\sqrt{\delta} W)$, where the crucial change in the proof is the upper bound on $Var(Z_j)$ in line 220 from $O(1/\epsilon^2)$ to $O(\delta)$.

For the partial prediction model, when $\epsilon = 1-\delta$ for small $\delta>0$, Theorem 4.2’s guarantee $\alpha_{RT} + (1 - \alpha_{RT} - o(1))(2\epsilon - \epsilon^2)$ becomes $1 - O(\delta^2)$.

We will try to mention the above results in the final version of the paper.

• What is the intuition for why predictions are not needed for narrow instances?

For this discussion, consider unweighted graphs. Algorithms improving on GW for low-degree graphs use two ideas: a stronger SDP relaxation using triangle inequalities, and a local search after rounding. The GW SDP has a tight integrality gap even on degree-2 instances, so using the stronger SDP is unavoidable. Why does local search help on low-degree graphs? Well, for high-degree vertices, tail concentration typically forces each vertex to have more neighbors on the other side of the cut after rounding. But this is not the case for low-degree graphs because concentration bounds are weaker, which means that locally improving moves is a viable strategy for improving the rounded solution with non-trivial probability. For a longer discussion, please see the paper of Feige, Karpinski, and Langberg that gave the first algorithm to beat the GW bound on low-degree graphs.

For weighted graphs, all this intuition carries over, but we need to be careful how the weight of the edges incident to a vertex are distributed: whether it is concentrated on a few edges (“narrow”) or is spread over many edges (“wide”). (We will add the intuition in the next version of the paper.)

We thank the reviewer for the comments and constructive encouragement.

• Could you please motivate more about the advantages of utilizing predictions in the offline setting with practical applications?

Predictions in both the offline and online settings help overcome worst-case outcomes by providing additional information about a specific instance. In the offline setting, predictions help bypass computational lower bounds as against information-theoretic ones online. In practice, predictions for offline problems model different scenarios; we list three examples here: They can be generated by machine learning models based on solving similar instances previously. This is common for applications such as revenue optimization in auctions. They can be used to model advice received from domain experts. They can be used to model settings in which a first, coarse solution has already been computed. An algorithm can take advantage of this information to provide a “warm start” without repeating the possibly expensive computation.

• How does your setup differ from the works of [Bampis et al., 2024] and [Ghoshal et al., 2024]?

The parallel work of [Bampis et al] considers dense instances of certain maximization problems, including max-cut. Their notion of dense instances have $\Omega(n^2)$ edges (whereas our max-cut results are for general instances). This high density allows them to use advice from only a poly-logarithmic number of calls to the oracle. Moreover, their focus is improving the running time of the PTAS algorithms, whereas our focus is on getting improvements to the approximation guarantees.

The independent and unpublished work of [Ghoshal et al.] considers a model very similar to ours. The original version of their work (concurrent to ours) considered dense cases of max-cut and the closely related max-2LIN. Their notion of density is much weaker than Bampis et al, and is similar to our notion of wide instances. A more recent version (subsequent to ours, and uploaded last week) of their paper gives algorithms for dense instances of 3LIN (and hardness for 4LIN), in contrast to our work that goes in the direction of exploring more general 2CSPs.

• Do you think it is possible to define a computational upper bound on the cost of getting the predictions so that an approximation algorithm can still be considered polynomial? In other words, can there be a trade-off between the cost of predictions and the improvement on the worst-case bound?

The computational hardness of Max-Cut (in particular the Unique-Games hardness) means that any polynomial-time approximation algorithm would have an approximation guarantee no better than $\alpha_{GW}$. Hence, we cannot restrict the algorithm to polynomial computation in a standard sense. It would definitely be interesting to consider a model with “parsimonious predictions” where we count the number of queries (say $Q$) made to the prediction oracle, and then study the approximation factor as a function of both the parameter $\varepsilon$ and $Q$. Note that since we are counting calls to an oracle instead of computation time, the hardness results for polynomial-time algorithms are no longer relevant in this setting. The parallel work of Bampis et al. considers parsimonious predictions for dense instances of max-cut with quadratically many edges, and it may also be interesting to consider it for general instances; this seems like a cool direction to explore!