Unweighted Stochastic Local Search can be Effective for Random CSP Benchmarks
We present ULSA, a novel stochastic local search algorithm for random binary constraint satisfaction problems (CSP). ULSA is many times faster than the prior state of the art on a widely-studied suite of random CSP benchmarks. Unlike the best previous methods for these benchmarks, ULSA is a simple unweighted method that does not require dynamic adaptation of weights or penalties. ULSA obtains new record best solutions satisfying 99 of 100 variables in the challenging frb100-40 benchmark instance.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
From random walks to distances on unweighted graphs
Large unweighted directed graphs are commonly used to capture relations between entities. A fundamental problem in the analysis of such networks is to properly define the similarity or dissimilarity between any two verti…
ClusteringVolume Doubling Condition and a Local Poincaré Inequality on Unweighted Random Geometric Graphs
The aim of this paper is to establish two fundamental measure-metric properties of particular random geometric graphs. We consider $\varepsilon$-neighborhood graphs whose vertices are drawn independently and identically …
Local optimisation of Nyström samples through stochastic gradient descent
We study a relaxed version of the column-sampling problem for the Nystr\"om approximation of kernel matrices, where approximations are defined from multisets of landmark points in the ambient space; such multisets are re…
Density estimation from unweighted k-nearest neighbor graphs: a roadmap
Consider an unweighted k-nearest neighbor graph on n points that have been sampled i.i.d. from some unknown density p on R^d. We prove how one can estimate the density p just from the unweighted adjacency matrix of the…
Density EstimationNLocalSAT: Boosting Local Search with Solution Prediction
The Boolean satisfiability problem (SAT) is a famous NP-complete problem in computer science. An effective way for solving a satisfiable SAT problem is the stochastic local search (SLS). However, in this method, the init…
Prediction