Theory of local search

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureHoofdstukAcademicpeer review

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.

TaalEngels
TitelHandbook of heuristics
RedacteurenR. Martí, P. Pardalos, M. Resende
Plaats van productieCham
UitgeverijSpringer
Pagina's299-339
Aantal pagina's41
ISBN van elektronische versie978-3-319-07124-4
ISBN van geprinte versie978-3-319-07123-7
DOI's
StatusGepubliceerd - 13 aug 2018

Vingerafdruk

Combinatorial optimization
Local Search
Heuristic methods
Combinatorial Optimization Problem
Computational complexity
Heuristic Method
Tabu search
Game theory
Simulated annealing
Worst-case Performance
Polynomials
Local Search Algorithm
Tabu Search
Game Theory
Simulated Annealing
Polynomial time
Computational Complexity
NP-complete problem
Optimal Solution
Local search (optimization)

Trefwoorden

    Citeer dit

    Michiels, W., Aarts, E. H. L., & Korst, J. (2018). Theory of local search. In R. Martí, P. Pardalos, & M. Resende (editors), Handbook of heuristics (blz. 299-339). Cham: Springer. DOI: 10.1007/978-3-319-07124-4_6
    Michiels, W. ; Aarts, E.H.L. ; Korst, Jan. / Theory of local search. Handbook of heuristics. redacteur / R. Martí ; P. Pardalos ; M. Resende. Cham : Springer, 2018. blz. 299-339
    @inbook{c5a05cb9b6d84585be1c3620bbfeeda9,
    title = "Theory of local search",
    abstract = "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.",
    keywords = "Iterative improvement, Performance ratio, PLS, Time complexity",
    author = "W. Michiels and E.H.L. Aarts and Jan Korst",
    year = "2018",
    month = "8",
    day = "13",
    doi = "10.1007/978-3-319-07124-4_6",
    language = "English",
    isbn = "978-3-319-07123-7",
    pages = "299--339",
    editor = "R. Mart{\'i} and P. Pardalos and M. Resende",
    booktitle = "Handbook of heuristics",
    publisher = "Springer",
    address = "Germany",

    }

    Michiels, W, Aarts, EHL & Korst, J 2018, Theory of local search. in R Martí, P Pardalos & M Resende (redactie), 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.

    Handbook of heuristics. redactie / R. Martí; P. Pardalos; M. Resende. Cham : Springer, 2018. blz. 299-339.

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureHoofdstukAcademicpeer 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 -

    Michiels W, Aarts EHL, Korst J. Theory of local search. In Martí R, Pardalos P, Resende M, redacteurs, Handbook of heuristics. Cham: Springer. 2018. blz. 299-339. Beschikbaar vanaf, DOI: 10.1007/978-3-319-07124-4_6