BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.3.6//EN
BEGIN:VEVENT
UID:960@lincs.fr
DTSTART;TZID=Europe/Paris:20260924T140000
DTEND;TZID=Europe/Paris:20260924T150000
DTSTAMP:20260928T113646Z
URL:https://www.lincs.fr/events/stochastic-multi-robot-monitoring-on-graph
 s-under-markovian-mobility/
SUMMARY:Stochastic Multi-Robot Monitoring on Graphs under Markovian
 Mobility
DESCRIPTION:Stochastic Multi-Robot Monitoring on Graphs under Markovian
 Mobility\n\nWe study a stochastic multi-robot monitoring problem on a
 connected graph G = (V\, E)\, where each robot moves according to a Markov
 chain on G and monitors the closed neighborhood of its current vertex. The
 performance of r robots is evaluated in steady state via two objectives:
 average-case coverage (the expected number of covered vertices) and
 worst-case coverage (the minimum coverage probability over all vertices).
 We consider three models: independent homogeneous strategies\, where all
 robots share the same stationary distribution\; independent heterogeneous
 strategies\, where robots use different stationary distributions\; and
 centralized strategies\, allowing arbitrary correlations between robot
 locations.\n\nFor the heterogeneous model\, we prove that maximizing
 average coverage is NP-hard even for two robots\, and that replicating an
 easy-to-compute optimal homogeneous strategy yields a (1 ? (1 ?
 1/r)^r)-approximation for both objective functions in the heterogeneous
 setting\; moreover\, no polynomial-time algorithm can achieve a ratio
 better than 1 ? 1/e unless P = NP.\n\nCentralized strategies can exploit
 correlations to reduce redundancy. We develop a hierarchy of approximation
 factors: for any positive integer r' ? r\, writing r = h r' + b with 0 ? b
 &lt\; r'\, block coordination yields a [1 ? (1 ? r'/r)^h (1 ?
 b/r)]-approximation for both objectives. We also establish NP-hardness and
 a tight 1 ? 1/e inapproximability bound. Moreover\, we prove
 diminishing-returns properties with respect to the number of robots: a
 non-increasing-ratio property holds for the average-case objective in all
 settings\, but not for the heterogeneous worst-case objective. These
 results provide a unified complexity and approximation landscape for
 stochastic graph monitoring and quantify the benefit of heterogeneity and
 coordination in steady-state multi-robot monitoring.\n\nJoint work with
 Walid Ben-Ameur and Tijani Chahed.\n\narXiv:2608.20618
CATEGORIES:Seminars,Youtube
LOCATION:Amphi 2\, 19 place Marguerite Perey\, Palaiseau\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=19 place Marguerite Perey\,
 Palaiseau\, France;X-APPLE-RADIUS=100;X-TITLE=Amphi 2:geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20260329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR