Browse

A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search

DC Field Value Language
dc.contributor.authorHong, Sung-Pil-
dc.contributor.authorCho, Sung-Jin-
dc.contributor.authorPark, Myoung-Ju-
dc.date.accessioned2009-07-08T06:23:49Z-
dc.date.available2009-07-08T06:23:49Z-
dc.date.issued2007-11-06-
dc.identifier.citationEuropean Journal of Operational Research 193 (2009) 351-364en
dc.identifier.issn0377-2217-
dc.identifier.urihttp://hdl.handle.net/10371/5336-
dc.description.abstractWe propose a new heuristic for the single-searcher path-constrained discrete-time Markovian-target search. The algorithm minimizes
an approximate, instead of exact, nondetection probability computed from the conditional probability that reflects the search history
over the time windows of a fixed length, l. Having a pseudo-polynomial complexity, it can solve, in reasonable time, the instances an
order of magnitude larger than those solved in the previous studies. By an asymptotic analysis relying on the fast-mixing Markov chain,
we show that the relative error of the approximation exponentially diminishes as l increases and the experimental results confirm the
analysis. The experiment also reveals a correlation very close to 1 between the approximate and exact nondetection probability of a
search path. This means that the heuristic produces near-optimal search paths.
en
dc.description.sponsorshipThe research was partially supported by KOSEF research fund R01-2005-000-10271-0.
The research was partially supported by the Second Stage of Brain Korea 21 Project in 2007.
www.elsevier.com/locate/ejor
Available online at www.sciencedirect.com
European Journal of Operational Research 193 (2009) 351–364
en
dc.language.isoen-
dc.publisherElsevieren
dc.subjectSearch theoryen
dc.subjectHeuristicsen
dc.subjectMarkov processesen
dc.subjectNetwork flowsen
dc.titleA pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target searchen
dc.typeArticleen
dc.contributor.AlternativeAuthor홍성필-
dc.contributor.AlternativeAuthor조성진-
dc.contributor.AlternativeAuthor박명주-
dc.identifier.doi10.1016/j.ejor.2007.10.048-
dc.identifier.doi10.1016/j.ejor.2007.10.048-
dc.citation.journaltitleEuropean Journal of Operational Research-
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
Files in This Item:
There are no files associated with this item.
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse