BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Eurandom - ECPv4.9.1.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Eurandom
X-ORIGINAL-URL:https://www.eurandom.tue.nl
X-WR-CALDESC:Events for Eurandom
BEGIN:VEVENT
DTSTART;TZID=UTC+0:20181211T124500
DTEND;TZID=UTC+0:20181211T134500
DTSTAMP:20190519T065758
CREATED:20181205T105010Z
LAST-MODIFIED:20181205T105037Z
UID:2378-1544532300-1544535900@www.eurandom.tue.nl
SUMMARY:Eindhoven Stochastics Colloquium
DESCRIPTION:Stefan Klootwijk (University of Twente) \nOn Random Shortest Path Metrics \nSimple heuristics often show a remarkable performance in practice for optimization problems. Worst-case analysis often falls short of explaining this performance. Because of this\, "beyond worst-case analysis" of algorithms has recently gained a lot of attention\, including probabilistic analysis of algorithms. The instances of many optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space\, which provides a structure that is usually heavily exploited in the analysis. However\, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other\, more realistic\, distributions. \nIn this talk we take a look at another class of metric spaces\, namely random shortest path metrics. A random shortest path metric is constructed by drawing independent random edge weights for each edge in a given graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. This model is also known as first passage percolation. We derive some properties of such metrics\, and look at the performance of some simple heuristics for the minimum distance perfect matching problem\, the traveling salesman problem\, and the k-median problem on instances obtained from such metrics. \nhttp://www.win.tue.nl/StoSem/ \n
URL:https://www.eurandom.tue.nl/event/eindhoven-stochastics-colloquium-2/
LOCATION:MF 12 (4th floor MetaForum Building\, TU/e
CATEGORIES:STO Colloquium
END:VEVENT
END:VCALENDAR