BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal: Date iCal//NONSGML kigkonsult.se iCalcreator 2.16.12//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Ical
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:STANDARD
DTSTART:20191103T020000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RDATE:20201101T020000
TZNAME:EST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20200308T020000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.1467118.field_date.0@crcs.seas.harvard.edu
DTSTAMP:20200810T115024Z
DESCRIPTION:\n Security Games: Quasi-Regular Sequences\, and a New Version o
f TSP\n\n\n\n [joint work with Leonard J. Schulman and Omer Tamuz (SODA 201
8) and with Mark Klein (submitted)]In security games\, a defender commits
to a mixed strategy for protecting a set of n targets of values v_i\; an a
ttacker\, knowing the defender's strategy\, chooses which target to attack
and for how long. We study a natural version in which the attacker's util
ity grows linearly with the time he spends at the target\, but drops to 0
if he is caught. The defender's goal is to minimize the attacker's utility
. The defender's strategy consists of a schedule for visiting the targets\
; a metric space determines how long it takes to travel between targets. S
uch games naturally model a number of real-world scenarios\, including pro
tecting computer networks from intruders\, animals from poachers\, etc. We
study this problem in two scenarios:\n\n\n\n 1. When all the distances bet
ween targets are the same\, then optimal and near-optimal strategies natur
ally correspond to sequences in which each character occupies a prescribed
fraction p_i of the sequence\, and appears 'close to evenly spread.'We fo
rmalize these notions\, and give efficient algorithms for finding sequence
s whose properties are strong enough to provide optimal or near-optimal st
rategies in the corresponding security game.\n\n\n\n 2. When distances betw
een targets are arbitrary\, the problem subsumes the well-known Traveling
Salesman Problem (TSP)\, but generalizes it in novel and interesting ways.
We give a polynomial-time O(log n) approximation algorithm for finding th
e best strategy for the defender.\n\n\n\n David Kempe received his Ph.D. fr
om Cornell University in 2003\, and has been on the faculty in the compute
r science department at USC since the Fall of 2004\, where he is currently
an Associate Professor. His primary research interests are in computer sc
ience theory and the design and analysis of algorithms\, with a particular
emphasis on social networks\, algorithms related to online and other lear
ning models\, and game-theoretic and pricing questions. He is a recipient
of the NSF CAREER award\, the VSoE Junior Research Award\, the ONR Young I
nvestigator Award\, a Sloan Fellowship\, and an Okawa Fellowship\, in addi
tion to several USC mentoring awards and Best Paper awards.\n\n
DTSTART;TZID=America/New_York:20191113T140000
DTEND;TZID=America/New_York:20191113T150000
LAST-MODIFIED:20191002T163053Z
LOCATION:Pierce Hall 209
SUMMARY:David Kempe: Security Games: Quasi-Regular Sequences\, and a New Ve
rsion of TSP
URL;TYPE=URI:https://crcs.seas.harvard.edu/event/david-kempe-security-games
-quasi-regular-sequences-and-new-version-tsp
END:VEVENT
END:VCALENDAR