Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 20, 2020, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Konstantinos Panagiotou (University of Munich)
We introduce and study the general setting of weighted search in which a number of targets, each equipped with a certain weight, are hidden in a star-like environment that consists of m infinite, concurrent rays, that have a common origin. A mobile searcher, initially located at the origin, must explore this environment so as to locate a set of targets whose aggregate weight is at least a given value W. The cost of the search strategy is defined as the total distance traversed by the searcher, and its performance is evaluated by the worst-case ratio of the cost incurred by the searcher over the cost of an on optimal, offline strategy with complete access to the instance. This setting encompasses several problems in search theory; namely, the problem in which only a single target is sought, as well as the problem in which all targets have unit weights.
In this work we present and analyze a search strategy of optimal performance. We observe that the known approaches for unweighted search that rely on geometrically increasing search depths perform very poorly in the context of weighted search. We bypass this problem by using a strategy that modifies the search depths adaptively, depending on the number of targets located up to the current point in time.
This is joint work with S. Angelopoulos.
Automatic MiSe System Software Version 1.4803M | admin login