# Reactive Local Search for the Maximum Clique Problem1

@article{Battiti2001ReactiveLS, title={Reactive Local Search for the Maximum Clique Problem1}, author={Roberto Battiti and Marco Protasi}, journal={Algorithmica}, year={2001}, volume={29}, pages={610-637} }

Abstract. A new Reactive Local Search (\RLS ) algorithm is proposed for the solution of the Maximum-Clique problem. \RLS is based on local search complemented by a feedback (history-sensitive) scheme to determine the amount of diversification. The reaction acts on the single parameter that decides the temporary prohibition of selected moves in the neighborhood, in a manner inspired by Tabu Search. The performance obtained in computational tests appears to be significantly better with respect to… Expand

#### Topics from this paper

#### 267 Citations

Reactive and dynamic local search for max-clique: Engineering effective building blocks

- Computer Science, Mathematics
- Comput. Oper. Res.
- 2010

An ongoing investigation about how different algorithmic building blocks contribute to solving the maximum clique problem is presented, showing the crucial effects of the implementation, the robustness of different techniques, and their empirical scalability. Expand

Dynamic Local Search for the Maximum Clique Problem

- Mathematics, Computer Science
- J. Artif. Intell. Res.
- 2006

It is shown empirically that DLSMC achieves substantial performance improvements over state-of-the-art algorithms for the maximum clique problem over a large range of the commonly used DIMACS benchmark instances. Expand

Reactive and dynamic local search for Max-Clique , an experimental comparison

- 2007

This paper presents results of an ongoing investigation about how different algorithmic building blocks contribute to solving the Maximum Clique problem. We consider greedy constructions, plateau… Expand

Target Aware Local Search for Maximum Clique Problem

- Mathematics
- 2014

This paper presents a simple algorithm (TALS) for solving the maximum clique problem. The algorithm is based on multi restart and local optimization techniques. The diversification in order to avoid… Expand

Reactive Local Search Techniques for the Maximum k-conjunctive Constraint Satisfaction Problem (MAX-k-CCSP)

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1999

The performance of the Hamming-based Reactive Tabu Search algorithm (H-RTS) previously proposed for the Maximum Satisfiability problem is studied for the different Maximum k-Conjunctive Constraint Satisfaction problem. Expand

Phased local search for the maximum clique problem

- Mathematics, Computer Science
- J. Comb. Optim.
- 2006

Phased Local Search has no problem instance dependent parameters and achieves state-of-the-art performance for the maximum clique problem over a large range of the commonly used DIMACS benchmark instances. Expand

R-EVO: A Reactive Evolutionary Algorithm for the Maximum Clique Problem

- Computer Science, Mathematics
- IEEE Transactions on Evolutionary Computation
- 2011

It is demonstrated that the combination of the estimation-of-distribution concept with RSO produces significantly better results than EA/G for many test instances and it is remarkably robust with respect to the setting of the algorithm parameters. Expand

An Efficient Local Search for the Feedback Vertex Set Problem

- Computer Science, Mathematics
- Algorithms
- 2013

NewkLS FVS (LS, local search; FVS, feedback vertex set), a variable depth-based local search algorithm with a randomized scheme to optimize the efficiency and performance is presented. Expand

Greedy, Prohibition, and Reactive Heuristics for Graph Partitioning

- Computer Science, Mathematics
- IEEE Trans. Computers
- 1999

New heuristic algorithms are proposed for the Graph Partitioning problem and detailed experimental results are presented on benchmark suites used in the previous literature, consisting of graphs derived from parametric models and of "real-world" graphs of large size. Expand

Reactive and dynamic local search for Max-Clique, does the complexity pay off?

- Computer Science
- 2006

The experimental results consider both the empirical hardness, measured by the iterations needed to reach empirical maxima, and the CPU time per iteration, in particular the recently proposed technique of Dynamic Local Search and the previously proposed Reactive Local Search. Expand

#### References

SHOWING 1-10 OF 39 REFERENCES

Greedy, Prohibition, and Reactive Heuristics for Graph Partitioning

- Computer Science, Mathematics
- IEEE Trans. Computers
- 1999

New heuristic algorithms are proposed for the Graph Partitioning problem and detailed experimental results are presented on benchmark suites used in the previous literature, consisting of graphs derived from parametric models and of "real-world" graphs of large size. Expand

Reactive search, a history-sensitive heuristic for MAX-SAT

- Mathematics, Computer Science
- JEAL
- 1997

A new RS algorithm is proposed for the approximated solution of the Maximum Satisfiability problem: a component based on local search with temporary prohibitions (Tabu Search) is complemented with a reactive scheme that determines the appropriate value of the prohibition parameter by monitoring the Hamming distance along the search trajectory. Expand

The Reactive Tabu Search

- Mathematics, Computer Science
- INFORMS J. Comput.
- 1994

An algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search, and it is shown that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant. Expand

Applying the INN model to the Maximum Clique problem

- Computer Science
- Cliques, Coloring, and Satisfiability
- 1993

The work presented here is a development and improvement of a neural network algorithm and an improved version of the t-A algorithm that was introduced recently that are applied to the max-clique problem. Expand

Solving the maximum clique problem using a tabu search approach

- Mathematics, Computer Science
- Ann. Oper. Res.
- 1993

Two variants of a tabu search heuristic are described, a deterministic one and a probabilistic one, for the maximum clique problem, which produces graphs with larger clique sizes than comparable ones obtained by classical random graph generating techniques. Expand

Approximation Algorithms for Combinatorial Problems

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1974

For the problem of finding the maximum clique in a graph, no algorithm has been found for which the ratio does not grow at least as fast as n^@e, where n is the problem size and @e>0 depends on the algorithm. Expand

Approximately solving Maximum Clique using neural network and related heuristics

- Mathematics, Computer Science
- Cliques, Coloring, and Satisfiability
- 1993

One of these algorithms, Mean Field Annealing, is implemented on the Connection Machine CM-5 and a fast annealing schedule is experimentally evaluated on random graphs, as well as on several benchmark graphs, and on Sanchis graphs. Expand

Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning

- Mathematics, Computer Science
- Oper. Res.
- 1991

This is the second in a series of three papers that empirically examine the competitiveness of simulated annealing in certain well-studied domains of combinatorial optimization. Simulated annealing… Expand

Tabu Search - Part I

- Computer Science
- INFORMS J. Comput.
- 1989

The fundamental principles underlying tabu search as a strategy for combinatorial optimization problems are presented and more advanced considerations are examined, applying the basic ideas to special settings and outlining a dynamic move structure to insure finiteness. Expand

Computer solutions of the traveling salesman problem

- Mathematics
- 1965

Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer. The first produces guaranteed optimal solution for problems… Expand