[Theory] [Theory Lunch] Yury Makarychev, Wednesday, 11/13 12-1pm, JCL 390

[Gabe Schoenbach via Theory]

Hi all — please join us this *Wednesday at 12pm* for theory lunch! Details
below:

***
*Date: *November 13, 2024, 12pm
*Location: *JCL 390

*Title: *Shortest Path, Asymmetric TSP, and Group Steiner Tree with Vector
Costs

*Speaker: *Yury Makarychev (TTIC)

*Abstract:* 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.

We present polylogarithmic-approximation algorithms as well as hardness of
approximation results.

Based on joint work with Max Ovsiankin and Erasmo Tani.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241111/b0500b03/attachment.html>