×
Llewellyn, Donna Crystal; Tovey, Craig; Trick, Michael

Local optimization on graphs. (English) Zbl 0675.90085

Discrete Appl. Math. 23, No. 2, 157-178 (1989).
This paper is devoted to the study of the complexity of finding a local optimum of an arbitrary function over a neighborhood graph. Some kind of two-person game is introduced to yield an estimation of the amount of work needed to find a local optimum.
Reviewer: W.-X.Li

Cited in 1 Review
Cited in 26 Documents

MSC:

90C35 Programming involving graphs or networks
05C99 Graph theory
68Q25 Analysis of algorithms and problem complexity
91A05 2-person games
68W99 Algorithms in computer science
91A80 Applications of game theory
68R10 Graph theory (including graph drawing) in computer science

Keywords:

heuristic; polynomial time local search; local optimum; neighborhood graph
PDF BibTeX XML Cite
\textit{D. C. Llewellyn} et al., Discrete Appl. Math. 23, No. 2, 157--178 (1989; Zbl 0675.90085)
Full Text: DOI

References:

[1] Aldous, D., Minimization algorithms and random walk on the \(d\)-cube, Tech. Rept., University of California, Berkeley, CA (1981)
[2] Beineke, L. W.; Harary, F., The genus of the \(n\)-cube, Canad. J. Math., 17, 494-496 (1965) · Zbl 0127.13801
[3] Danzer, L.; Klee, V., Lengths of snakes in boxes, J. Combinat. Theory, 2, 258-265 (1967) · Zbl 0153.54202
[4] Djidjev, H., On the problem of partitioning planar graphs, SIAM J. Alg. Dis. Meth., 229-240 (1982) · Zbl 0503.05057
[5] Dobkin, D.; Lipton, R., Multidimensional searching problems, SIAM J. Comput., 5, 2, 181-186 (1976) · Zbl 0333.68031
[6] Feller, W., (An Introduction to Probability Theory and Its Applications, 1 (1971), Wiley: Wiley New York) · Zbl 0138.10207
[7] Garey, M.; Johnson, D., Computers and Intractibility: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA
[8] Gilbert, J. R.; Hutchinson, J. P.; Tarjan, R. E., A separator theorem for graphs of bounded genus, J. Algorithms, 5, 3, 391-407 (1984) · Zbl 0556.05022
[9] Hausmann, D.; Korte, B., Lower bounds on the worst-case complexity of some oracle algorithms, Discrete Math., 24, 261-276 (1978) · Zbl 0392.68036
[10] Johnson, D.; Papadimitriou, C.; Yannakakis, M., How easy is local search?, (Proceeding IEEE Symposium on the Foundations of Computer Science (1985)), 39-42
[12] Lipton, R.; Rose, D.; Tarjan, R., Generalized nested dissection, SIAM J. Numer. Anal., 16, 2, 346-358 (1979) · Zbl 0435.65021
[13] Murty, K. G.; Kabadi, S. N., Some NP-complete problems in quadratic and nonlinear programming, Math. Programming, 39, 2, 117-130 (1987) · Zbl 0637.90078
[14] Nemhauser, G.; Wolsey, L., Best algorithms for approximating the maximum of a submodular set function, Math. Oper. Res., 3, 177-188 (1978) · Zbl 0395.90072
[15] Papadimitriou, C.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060
[16] Ringel, G., Das Geschlecht des Vollständigen Paaren Graphen, A.B.H. Math. Sem. Univ. Hamburg, 28, 139-150 (1965) · Zbl 0132.21203
[17] Tovey, C. A., A simplified NP-complete satisfiability problem, Discrete Appl. Math., 8, 85-89 (1984) · Zbl 0534.68028
[18] Tovey, C. A., Low order polynomial bounds on the expected performance of local improvement algorithms, Math. Programming, 35, 2, 193-224 (1986) · Zbl 0613.90065
[19] Wood, G. R., Multidimensional bisection and global minimization, Tech. Rept., University of Canterbury (1985)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.