Local optimization on graphs

Donna Crystal Llewellyn; Craig Tovey; Michael Trick

doi:10.1016/0166-218X(89)90025-5

Local optimization on graphs

Donna Crystal Llewellyn, Craig Tovey, Michael Trick

Institute for Inclusive and Transformative Scholarship

Research output: Contribution to journal › Article › peer-review

51 Scopus citations

Abstract

The complexity of finding local optima is an open problem for many neighborhood structures. We show how to derive close lower and upper bounds on the minimum number of function evaluations needed to find a local optimum in an arbitrary graph. When these bounding techniques are applied to the hypercube, the results give insights into the class PLS and the gap between the average and worst-case behavior of local search.

Original language	English
Pages (from-to)	157-178
Number of pages	22
Journal	Discrete Applied Mathematics
Volume	23
Issue number	2
DOIs	https://doi.org/10.1016/0166-218X(89)90025-5
State	Published - May 1989

Access to Document

10.1016/0166-218X(89)90025-5

Cite this

@article{1a591ea53c3346fa85f7e7ecf73714a4,

title = "Local optimization on graphs",

abstract = "The complexity of finding local optima is an open problem for many neighborhood structures. We show how to derive close lower and upper bounds on the minimum number of function evaluations needed to find a local optimum in an arbitrary graph. When these bounding techniques are applied to the hypercube, the results give insights into the class PLS and the gap between the average and worst-case behavior of local search.",

author = "Llewellyn, {Donna Crystal} and Craig Tovey and Michael Trick",

year = "1989",

month = may,

doi = "10.1016/0166-218X(89)90025-5",

language = "English",

volume = "23",

pages = "157--178",

number = "2",

}

TY - JOUR

T1 - Local optimization on graphs

AU - Llewellyn, Donna Crystal

AU - Tovey, Craig

AU - Trick, Michael

PY - 1989/5

Y1 - 1989/5

N2 - The complexity of finding local optima is an open problem for many neighborhood structures. We show how to derive close lower and upper bounds on the minimum number of function evaluations needed to find a local optimum in an arbitrary graph. When these bounding techniques are applied to the hypercube, the results give insights into the class PLS and the gap between the average and worst-case behavior of local search.

AB - The complexity of finding local optima is an open problem for many neighborhood structures. We show how to derive close lower and upper bounds on the minimum number of function evaluations needed to find a local optimum in an arbitrary graph. When these bounding techniques are applied to the hypercube, the results give insights into the class PLS and the gap between the average and worst-case behavior of local search.

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

U2 - 10.1016/0166-218X(89)90025-5

DO - 10.1016/0166-218X(89)90025-5

M3 - Article

AN - SCOPUS:38249022814

SN - 0166-218X

VL - 23

SP - 157

EP - 178

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2

ER -

Local optimization on graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this