### Uittreksel

Local search is a widely used method to solve combinatorial optimization problems. As many relevant combinatorial optimization problems are NP-hard, we often may not expect to find an algorithm that is guaranteed to return an optimal solution in a reasonable amount of time, i.e., in polynomial time. Therefore, one often resorts to heuristic methods that return good, suboptimal solutions in reasonable running times. Local search is a heuristic method that is popular for its ability to trade solution quality against computation time. By spending more time, we will generally get better solutions.Well-known examples of local search approaches are iterative improvement, simulated annealing, and tabu search. The performance of local search, in terms of quality or running time, may be investigated empirically, probabilistically, and from a worst-case perspective. In this chapter we focus on the last option. That is, we give provable results on the worst-case performance of local search algorithms. Besides combinatorial optimization problems, the theory discussed in this chapter also finds its application in game theory and computational complexity.

Taal | Engels |
---|---|

Titel | Handbook of heuristics |

Redacteuren | R. Martí, P. Pardalos, M. Resende |

Plaats van productie | Cham |

Uitgeverij | Springer |

Pagina's | 299-339 |

Aantal pagina's | 41 |

ISBN van elektronische versie | 978-3-319-07124-4 |

ISBN van geprinte versie | 978-3-319-07123-7 |

DOI's | |

Status | Gepubliceerd - 13 aug 2018 |

### Vingerafdruk

### Trefwoorden

### Citeer dit

*Handbook of heuristics*(blz. 299-339). Cham: Springer. DOI: 10.1007/978-3-319-07124-4_6

}

*Handbook of heuristics.*Springer, Cham, blz. 299-339. DOI: 10.1007/978-3-319-07124-4_6

**Theory of local search.** / Michiels, W.; Aarts, E.H.L.; Korst, Jan.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Hoofdstuk › Academic › peer review

TY - CHAP

T1 - Theory of local search

AU - Michiels,W.

AU - Aarts,E.H.L.

AU - Korst,Jan

PY - 2018/8/13

Y1 - 2018/8/13

N2 - Local search is a widely used method to solve combinatorial optimization problems. As many relevant combinatorial optimization problems are NP-hard, we often may not expect to find an algorithm that is guaranteed to return an optimal solution in a reasonable amount of time, i.e., in polynomial time. Therefore, one often resorts to heuristic methods that return good, suboptimal solutions in reasonable running times. Local search is a heuristic method that is popular for its ability to trade solution quality against computation time. By spending more time, we will generally get better solutions.Well-known examples of local search approaches are iterative improvement, simulated annealing, and tabu search. The performance of local search, in terms of quality or running time, may be investigated empirically, probabilistically, and from a worst-case perspective. In this chapter we focus on the last option. That is, we give provable results on the worst-case performance of local search algorithms. Besides combinatorial optimization problems, the theory discussed in this chapter also finds its application in game theory and computational complexity.

AB - Local search is a widely used method to solve combinatorial optimization problems. As many relevant combinatorial optimization problems are NP-hard, we often may not expect to find an algorithm that is guaranteed to return an optimal solution in a reasonable amount of time, i.e., in polynomial time. Therefore, one often resorts to heuristic methods that return good, suboptimal solutions in reasonable running times. Local search is a heuristic method that is popular for its ability to trade solution quality against computation time. By spending more time, we will generally get better solutions.Well-known examples of local search approaches are iterative improvement, simulated annealing, and tabu search. The performance of local search, in terms of quality or running time, may be investigated empirically, probabilistically, and from a worst-case perspective. In this chapter we focus on the last option. That is, we give provable results on the worst-case performance of local search algorithms. Besides combinatorial optimization problems, the theory discussed in this chapter also finds its application in game theory and computational complexity.

KW - Iterative improvement

KW - Performance ratio

KW - PLS

KW - Time complexity

UR - http://www.scopus.com/inward/record.url?scp=85063030709&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-07124-4_6

DO - 10.1007/978-3-319-07124-4_6

M3 - Chapter

SN - 978-3-319-07123-7

SP - 299

EP - 339

BT - Handbook of heuristics

PB - Springer

CY - Cham

ER -