Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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.

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

Previous talks by year: 2024 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