Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, February 20, 2020, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Konstantinos Panagiotou (University of Munich)

Weighted Online Search

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login