BEGIN:VCALENDAR
VERSION:2.0
METHOD:PUBLISH
CALSCALE:GREGORIAN
PRODID:-//WordPress - MECv7.9.0//EN
X-ORIGINAL-URL:https://optima.org.au/
X-WR-CALNAME:OPTIMA
X-WR-CALDESC:ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-PUBLISHED-TTL:PT1H
X-MS-OLK-FORCEINSPECTOROPEN:TRUE
BEGIN:VEVENT
CLASS:PUBLIC
UID:MEC-4e62e752ae53fb6a6eebd0f6146aa702@optima.org.au
DTSTART:20220330T050000Z
DTEND:20220330T060000Z
DTSTAMP:20220308T003900Z
CREATED:20220308
LAST-MODIFIED:20220329
PRIORITY:5
SEQUENCE:0
TRANSP:OPAQUE
SUMMARY:AI-based Optimisation Seminar Series 30 Mar 2022
DESCRIPTION:Speaker: Assoc. Prof. Julian Mestre, University of Sydney\nTitle: Theoretical Foundations of Profile Guided Binary Optimization\nSynopsis: Profile-guided binary optimization (PGO) is an effective technique in modern compiles to improve performance by optimizing how binary code is laid out in memory. At a very high level, the idea is to collect information about typical executions and then use this information to reorder how code blocks are laid out in memory to minimize instruction cache misses, which in turn translates into running time performance gains. Given a graph G=(V, E) where vertices represent blocks of code and edges represent jumps, the objective is to find an ordering of V leading to fast executions. Ext-TSP is an objective function over vertex orderings that has been empirically shown to be well correlated with performance gain of the reordered binary. The problem generalizes the classical MAX-TSP objective and the maximum bandwidth-bounded subgraph problem. We show that Ext-TSP is APX-hard to approximate in general, and we give a (k + 1)-approximation algorithm for general graphs and a PTAS for some sparse graph classes such as planar or treewidth-bounded graphs. Interestingly, the problem remains challenging even on very simple graph classes; indeed, there is no exact n^{o(k)} time algorithm for trees unless the ETH fails. We complement this negative result with an exact in n^{O(k)} time algorithm for trees. This is joint work with S. Pupyrev and S. W. Umboh.\n \nBio: Julian is an Associate Professor at the School of Computer Science at the University of Sydney and a Research Scientist at Meta. He is broadly interested in the design and analysis of efficient algorithms for combinatorial optimization problems such as covering, scheduling, routing and matching problems.\nWED 30 MAR 4 PM – 5 PM AEST\nZOOM Meeting ID: 873 1557 5255; Password: 778635\n
URL:https://optima.org.au/events/ai-based-optimisation-seminar-series-30-mar-2022/
CATEGORIES:Events
ATTACH;FMTTYPE=image/jpeg:https://optima.org.au/wp/wp-content/uploads/2022/03/Julian-event-media-1.jpg
END:VEVENT
END:VCALENDAR