[Theory] [TTIC Talks] 4/11 Research at TTIC: Yury Makarychev, TTIC

[Brandie Jones via Theory]

*When:         *April 11th *at 12:30pm CT  *


*Where:*        Talk will be given *live, in-person* at

                       TTIC, 6045 S. Kenwood Avenue

                        5th Floor, Room 530


*Virtually:*    via Panopto (Livestream
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=575ef65a-cfa4-4d55-b293-b1a901057b54>
)



*Who:*            Yury Makarychev, TTIC



*Title*:             From Scalars to Vectors: Approximability and Hardness
of ℓₚ-Shortest Path


*Abstract:*   We study vector-cost generalizations of classic combinatorial
optimization problems – Shortest Path, Group Asymmetric TSP, and Group
Steiner Tree. These problems model multi-resource optimization,
optimization under fairness constraints, or decision-making under
uncertainty. In our setting, each edge is assigned a cost vector with
non-negative components.


The cost of a feasible solution is defined by summing the cost vectors of
all edges in the solution and then computing the ℓₚ-norm of the resulting
vector. We present polylogarithmic-approximation algorithms as well as
hardness-of-approximation results. This talk is based on a joint paper with
Max Ovsiankin and Erasmo Tani, and an ongoing research project with Charlie
Carlson and Ron Mosenzon.


***********************************************************************************************

*Masks are optional in all common areas. **Full visitor guidance is
available at ttic.edu/visitors <http://ttic.edu/visitors>.*

***********************************************************************************************

*Research at TTIC Seminar Series*



TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended for students seeking
research topics and advisors and for the general TTIC and University of
Chicago communities interested in hearing what their colleagues are up to.


-- 
*Brandie Jones *
*Executive **Administrative Assistant*
Toyota Technological Institute
6045 S. Kenwood Avenue
Chicago, IL  60637
www.ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250404/3ca295a5/attachment-0001.html>