Abstract | ||
---|---|---|
We set up a general generic framework for local search algorithms. Then we show in this generic setting how heuristic, problem-specific
information can be used to improve the success probability of local search by focussing the search process on specific neighbor
states. Our main contribution is a result which states that stochastic local search using restarts has a provable complexity
advantage compared to deterministic local search. An important side aspect is the insight that restarting (starting the search
process all over, not using any information computed before) is a useful concept which was mostly ignored before.
|
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-73554-0_17 | Unconventional Computing |
Keywords | Field | DocType |
main contribution,restart,general generic framework,problemspecific information,provable complexity advantage,local search algorithm,search process,meta-algorithmics.,important side aspect,generic setting,heuristic information,stochastic local search,local search | Mathematical optimization,Incremental heuristic search,Guided Local Search,Beam search,Local search (optimization),Best-first search,Iterated local search,Mathematics,Tabu search,Iterative deepening depth-first search | Conference |
Volume | ISSN | ISBN |
4618 | 0302-9743 | 3-540-73553-4 |
Citations | PageRank | References |
3 | 0.48 | 4 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Uwe Schöning | 1 | 998 | 105.69 |