<div dir="ltr"><div dir="ltr">Hi all — please join us this <b>Wednesday at 12pm</b> for theory lunch! Details below:<div><br></div><div><div>***<br><b>Date: </b>November 13, 2024, 12pm<br><b>Location: </b>JCL 390<br><br><b>Title: </b>Shortest Path, Asymmetric TSP, and Group Steiner Tree with Vector Costs<br><br><b>Speaker: </b>Yury Makarychev (TTIC)<br><br><b>Abstract:</b> We study analogues of classic combinatorial optimization problems – Shortest Path, Group Asymmetric TSP, and Group Steiner Tree – with vector costs. In these problems, we assume that every edge has an associated cost vector with non-negative components. We define the cost of a feasible solution as follows. We add up cost vectors for all the edges in the solution and then compute the \ell_p-norm of the obtained vector.</div><br>We present polylogarithmic-approximation algorithms as well as hardness of approximation results.<br><br>Based on joint work with Max Ovsiankin and Erasmo Tani.</div></div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"></div></div></div></div></div>