CS Paper Radar

Exponential Local Search in Bounded-Occurrence MAX-CSP

Sophia Heimann, Hung P. Hoang, Stefan Hougardy

cs.DS cs.DMmath.CO ·submitted 2026-10-12 14:52 UTC · v1

Abstract

We study the number of improving steps that local search may require for $(2,2,r)$-MCA (Maximum Constraint Assignment), a bounded-occurrence version of MAX-CSP with valued constraints in which every constraint involves at most two variables, every variable occurs in at most two constraints, and every variable takes one of $r$ values. We consider the flip neighborhood, where two assignments are neighbors if they differ in the value of exactly one variable; moving to such a neighbor is called a flip. Local search repeatedly performs improving flips, that is, flips that strictly increase the objective value, until a local optimum is reached. Our main result is that $(2,2,5)$-MCA has the all-exp property: there is an infinite family of instances with initial assignments for which every sequence of improving flips ending in a local optimum has length exponential in the number of variables. Thus, on these instances, local search requires exponentially many steps regardless of which improving flip is chosen at each step. This is the first all-exp result for $(2,2,r)$-MCA for any value of $r$, and our result extends to every $r\ge 5$. In contrast, for $(2,2,2)$-MCA every sequence of improving flips has length at most quadratic in the number of variables~\cite{Kaz2020,KCJ2020}. We give a short, direct proof of this result.

Closest papers

Nearest neighbours by meaning across the whole index.

Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment

cs.DS math.CO ·2026-10-22 ·Sophia Heimann, Hung P. Hoang, Stefan Hougardy
theory similarity 0.79
Abstract · 37 pages

We prove the all-exp property for the Traveling Salesman Problem with the $2$-opt neighborhood, and for $(3,2,2)$- and $(2,3,2)$-Maximum Constraint Assignment with the flip neighborhood. The all-exp property states that infinitely many instances have an initial solution from which every sequence of improving moves to a local optimum, and hence every run of local search, has exponential length. For the Traveling Salesman Problem, the all-exp property was previously known for every $k$-opt neighborhood with $k \ge 3$, so our result for $2$-opt completes the picture for all $k$-kopt neighborhoods. In $(p,q,r)$-Maximum Constraint Assignment, each constraint involves at most $p$ variables, each variable occurs in at most $q$ constraints, and each domain has size $r$. Decreasing any of the parameters of $(3,2,2)$ or $(2,3,2)$ yields a problem in which every sequence of improving flips has polynomial length, so both Maximum Constraint Assignment results are tight. All three results settle long-standing open problems. Our proofs build on a common construction idea, which reveals a close connection between the local-search dynamics of the three problems.

0.11

Monotone Local Search with Sample-Dependent Running Times

cs.DS cs.DM ·2026-11-01 ·Serge Gaspers
theory similarity 0.60
Abstract · Companion site (including certificates and Lean formalization): https://serggasp.github.io/sample-MLS-site/ ; archived at https://doi.org/10…

Monotone Local Search turns an algorithm that extends a given partial solution into an algorithm that finds a solution from scratch: sample a few elements, hope that they lie in an unknown solution, and complete them. Its known analyses bound every call of the extension algorithm by a worst-case time that depends only on the number of sampled elements, and Esmer et al. (SODA 2024) showed that no algorithm that uses the extension algorithm as a black box with this running time beats the original form by more than a polynomial factor. We let this running time depend on the actual sample. If the extension algorithm decides in time $O^*(2^{g(I,X,k)})$, for a polynomial-time computable $g$, whether a sample $X$ can be completed to a solution with at most $k$ elements, our main theorem gives a randomized algorithm with one-sided error in time $O^*(2^{ψn})$ whenever, for some solution $S$ of size $k$ and some $t$, the exponential moment $\sum_{X\subseteq S,|X|=t}2^{-g(I,X,k)}$ is at least $2^{-ψn}\binom{n}{t}$. A corollary, multivariate Monotone Local Search, generalizes the theorems of Fomin et al. (STOC 2016, J. ACM 2019) and of Gaspers and Lee (ICALP 2017). For Max Leaf Spanning Tree and, equivalently, Connected Dominating Set, the previous best polynomial-space bound is $O^*(1.8619^n)$. Completing a sample is a Steiner tree problem, solved in time exponential in the number of terminals, which varies strongly with the sample. We obtain a randomized polynomial-space algorithm in time $O(1.6991^n)$ and a deterministic one in time $(\sqrt5-\frac12)^n 2^{o(n)}=O(1.7361^n)$. For connectivity problems in which the extension algorithm's running time doubles with every component of the sample, an analysis through a partition function gives randomized polynomial-space algorithms in time $O^*(1.8^n)$ for Connected Feedback Vertex Set and $O(1.6444^n)$ for Connected Vertex Cover.

0.26

Exact Locality Gaps for Matchable Semi-Matchings

cs.DS cs.DM ·2026-10-01 ·Marek Gałązka, Hanna Wdowicka
code/data similarity 0.59
Abstract · 11 pages. Verification code and data: https://github.com/mgalazka84/semimatching-locality-gaps

An assignment of tasks to servers can resist every small improvement and still make tasks wait longer than necessary. We determine exactly how inefficient such an assignment can be when each task requires one unit of service and the eligibility constraints permit all tasks to use distinct servers. For every move size $r$ and maximum current server load $K$, we give a closed formula for the worst ratio between locally optimal and globally optimal total completion time. Local optimality here allows every feasible reassignment changing at most $r$ tasks. Every finite-cap bound is attained on a tree where each task has at most two eligible servers. Thus the worst behavior already occurs under simple eligibility constraints. At load cap two, the exact ratio is $1+1/(r+2)$, attained on a path with $r+2$ tasks. Without a load cap, the worst-case supremum is $3/2$ for single-task moves and approximately $1.294503159$ for two-task moves; its excess above one is $1/(r+2)+O(2^{-r}/r)$ as $r$ grows. The proof uses an explicit rational potential on a comparison graph and matching extremal constructions. These results give sharp guarantees for bounded-size local search on matchable semi-matchings, including exact guarantees under degree bounds.

0.30

Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement

cs.AI ·2026-09-06 ·Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng, Trung Thanh Nguyen, Phuong Khanh Nguyen +1 more
benchmarktheory similarity 0.57
Abstract

Bounded-suboptimal search seeks a solution within a factor $w$ of optimal while reducing search effort. Focal Search (FS) uses heuristic guidance within FOCAL, the frontier nodes eligible under the threshold $w f_{\min}$, but its deterministic policy may leave $f_{\min}$ unchanged for many expansions. We introduce Probabilistic Focal Search (PFS), which follows the FS guided choice with probability $p$ and expands a minimum-$f$ OPEN node with probability $1-p$. The latter branch encourages the lower bound to advance, enlarging FOCAL and admitting nodes that may lead to feasible solutions. By balancing guidance and lower-bound advancement, this mechanism can reduce time to a bounded solution when progress is limited by delayed FOCAL admission. As a secondary transfer experiment, we apply the same scheduler to Dynamic Potential Search, yielding Probabilistic Dynamic Potential Search (PDPS). We benchmark PFS against FS on N-Puzzle, Pancake Sorting, and the Traveling Salesperson Problem (TSP), and evaluate its anytime extension on the Generalized Covering TSP (GCTSP), using multiple $w$ and $p$ values. Across these benchmarks, the largest gains occur when long $f_{\min}$ plateaus delay useful FOCAL admissions; in such settings, the probabilistic factor may reduce node expansions by about 90\% or more (e.g., on N-Puzzle and TSP). For the anytime algorithm family, Anytime Probabilistic Focal Search (APFS) outperforms all tested algorithms in evaluating anytime methods on GCTSP. We also observe that the benefit is smaller when the deterministic search already advances efficiently (e.g., Pancake Sorting), indicating that the probabilistic factor is most useful when FOCAL admission is a search bottleneck. The PDPS transfer shows that the mechanism also transfers to potential guidance, although its common-success effects remain domain- and bound-dependent.

0.20

Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse

cs.DS cs.LG ·2026-11-15 ·Vaneet Aggarwal
theory similarity 0.57
Abstract

We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every $ε>0$, we give an algorithm with recourse $O(ε^{-2})$ whose reported set has, at every time, expected value at least $1/4-ε$ times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above $1/4$, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above $1/4$ requires recourse that grows as a positive power of the cardinality budget. Thus $1/4$ is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was $3-2\sqrt2\approx0.172$. Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.

0.12

Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau

cs.AI ·2026-09-20 ·Alex Fukunaga
similarity 0.56
Abstract

In the A* search algorithm, the tie-breaking strategies for nodes with the same $f$-value determines which states A* expands on the final $f$-layer. For nine standard tie-breaking strategies, we show that under a consistent heuristic, every pair has positive-cost instances favoring each strategy over the other by an arbitrarily large additive expansion gap. A parameterized unit-cost grid example also gives unbounded expansion-count ratios between low-$h$ with FIFO and LIFO. In unit-cost search with $h > 0$ at non-goals, exact heuristic values near the goal lead to complementary extremal results: low-$h$ minimizes the number of remaining expansions from a common configuration within the perfect region, while high-$h$ maximizes the total number of expansions when every final-plateau state with $h=1$ is a goal predecessor. Finally, with the evaluation function $f_α = g + αh$, when $h>0$ at non-goals, every heuristic weight $0 \leq α<1$ eliminates tie-breaking sensitivity, and all tie-breaking strategies expand the same set of states.

0.27

Runtime Analysis of Cartesian Genetic Programming on Max: A Proven Exponential Speedup

cs.LG cs.AIcs.NE ·2026-11-11 ·Duc-Cuong Dang, Roman Kalkreuth, Andre Opris
publishedbenchmarktheory similarity 0.56
Abstract · Accepted as a poster at NeurIPS 2026. To appear in the conference proceedings

Genetic Programming (GP) is a search paradigm inspired from natural evolution for the automated discovery of expressions, functions, and computer programs. Cartesian GP (CGP) is a flavor of GP that uses a graph-based model to encode candidate programs, as contrasted to the conventional Tree-based GP (TGP). Since its inception two decades ago, CGP has predominantly been analyzed empirically, thus little is known regarding its theoretical performance guarantees. This paper analyzes CGP for the Max problem, which has been only rigorously studied for TGP with a proven expected runtime superlinear in the optimal program length $n$. We prove that the expected time for the ($1$+$1$) CGP employing common mutation operators to evolve an equivalent optimal of the same output is polylogarithmic in $n$, specifically at most $O(\log^9{n})$. This is remarkable, as it shows an exponential speedup by switching to CGP. Our results shed light on the benefit and the compactness of the graph-based representation for programs, and on how CGP can navigate its search and fitness spaces efficiently. This is a first proven performance guarantee for CGP on an established benchmark problem. Experiments complement our theoretical findings.

0.44

TSP instances that require exponentially many subtour elimination constraints

cs.DM math.CO ·2026-11-11 ·Eleonora Vercesi, Austin Buchanan
theory similarity 0.55
Abstract

We construct pathological TSP instances that require exponentially many subtour elimination constraints (SECs) in the sense that, if a smaller collection of SECs is imposed, then the Dantzig-Fulkerson-Johnson model returns a disconnected solution costing less than an optimal tour. For asymmetric instances on $n$ vertices, we prove a growth rate of \(Ω(φ^n)\), where \(φ\approx 1.618\) is the golden ratio. A node-splitting reduction gives metric instances with \(Ω(φ^{n/2})\) growth. We also give instances in the plane under the Euclidean, Rectilinear, and Maximum metrics that require exponentially many SECs. Concorde struggles on them, with solve times growing exponentially despite tiny integrality gaps.

0.28