id: 03924496
dt: j
an: 03924496
au: Wegener, Ingo
ti: Optimal search with positive switch cost is NP-hard.
so: Inf. Process. Lett. 21, 49-52 (1985).
py: 1985
pu: Elsevier Sciences Publishers (North-Holland), Amsterdam
la: EN
cc: 
ut: NP-hardness; optimal search; positive switch cost; optimal strategy
ci: 
li: doi:10.1016/0020-0190(85)90108-5
ab: Summary: We consider the problem of optimal search with positive switch
    cost. For vanishing switch cost we have efficient algorithms for the
    construction of an optimal strategy. We show here that already a very
    special subproblem with positive switch cost is NP-hard.
rv: