×

zbMATH — the first resource for mathematics

Local optimization on graphs. (English) Zbl 0675.90085
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

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
PDF BibTeX XML Cite
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., ()
[7] Garey, M.; Johnson, D., Computers and intractibility: A guide to the theory of NP-completeness, (1979), 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?, (), 39-42
[11] G. Leuker, Unpublished manuscript, Princeton University, Princeton, NJ (1976).
[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 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.