Monotone Local Search with Sample-Dependent Running Times
cs.DS, cs.DM
Submitted: 2026-11-01
Updated: 2026-11-01
Comments: Companion site (including certificates and Lean formalization): https://serggasp.github.io/sample-MLS-site/ ; archived at https://doi.org/10.5281/zenodo.23851002
Code: https://github.com/anthropics/formal-math
Project page: https://serggasp.github.io/sample-MLS-site
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Sources
- Constrained Multilinear Detection and Generalized Graph Motifs
- Solving connectivity problems parameterized by treewidth in single exponential time
- Deterministic parameterized connected vertex cover
- Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
- Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
- Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations
- Hoffman-London graphs: When paths minimize $H$-colorings among trees
- Long paths need not minimize $H$-colorings among trees
- Finding and counting vertex-colored subtrees
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Constrained multilinear detection for faster functional motif discovery
- Black-box Acceleration of Las Vegas Algorithms and Algorithmic Reverse Jensen's Inequalities
- The $k$-Leaf Spanning Tree Problem Admits a Klam Value of 39
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles