Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2013-14 > Star-search problems: new measures, algorithms and techniques
How to contact us


LSE 10 logo master_6

Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE


Enquiries: dom.events@lse.ac.uk 


Follow us online



Star-search problems: new measures, algorithms and techniques

Wednesday 4th June 2014, 4.00pm, 32L LG.14

Spyros Angelopoulosk

University Pierre et Marie Curie, Paris

Personal profile


We consider the problem of exploring a set of m concurrent rays using a single searcher. The rays are disjoint with the exception of a single common point, and in each ray a potential target may be located. The objective is to design efficient search strategies for locating the targets as quickly as possible.

In this talk I will describe results on two variants of this well-studied problem. In the first variant, the searcher must locate t targets (with t less than or equal to m ); this generalizes the setting in which only a single target is sought. The second variant corresponds to the setting in which the searcher incurs a fixed cost upon switching direction. For this problem, I will describe a proper use of infinite LP formulations that yields tight lower bounds.