harold@stretch.cs.mun.ca (Harold Wareham(Todd)) (12/07/90)
I am interested in references or reviews that deal with the following:
1) Assessing the computational complexity of optimization-problem
variants of decision problems
2) Assessing the computational complexity of solution-finding
variants of optimization problems
For example, for the Travelling Salesman Problem on a given instance,
the decision problem involves deciding whether or not a tour of length
<= B exists; the optimization problem involves determining the minimum
tour length B over all tours; and the solution-finding problem involves
returning at least one of these minimum-length tour (or alternatively,
all such tours).
I want to apply such techniques to several variants of the Graph
Steiner Tree problem on hypercubes which involve various degrees of
reticulate structure in the derived "tree".
My Steiner-Tree reference paper thus far is:
Foulds, L. R., and Graham, R. L. (1982) "The Steiner Problem in
phylogeny is NP-Complete". ADVANCES IN APPLIED MATHEMATICS,
3, 43-49.
Two technique papers that I have at the moment are:
Krentel, M. W. (1988) "The Complexity of Optimization Problems",
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 36, 490-509.
Leggett, E. W., Jr., and Moore, D. J. (1981) "Optimization Problems
and the Polynomial Hierarchy", THEORETICAL COMPUTER SCIENCE,
15, 279-289.
Any references on the topics above would be appreciated. Send E-mail
either to harold@stretch.cs.mun.ca (or, failing that, my BITNET
address, harold@kean.mun.ca). If there is enough interest, I will
post a summary.
Thanks in advance. Happy holidays!
- (Harold) Todd Wareham