2 papers
cs.DS2026
A simple Path-based LP Relaxation for Directed Steiner Tree
Kanstantsin Pashkovich, Marta Pozzi, Laura SanitÃ
We study the Directed Steiner Tree (DST) problem in layered graphs through a simple path-based linear programming relaxation. This relaxation achieves an integrality gap of O(l log…
math.OC2024
Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity
Alexander Tyurin, Marta Pozzi, Ivan Ilin +1
We consider nonconvex stochastic optimization problems in the asynchronous centralized distributed setup where the communication times from workers to a server can not be ignored,…