4 papers
Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
Liam Roditty, Ariel Sapir
We introduce a generalized family of $\left( 2\cdot \left\lfloor \frac{k}{2} \right\rfloor-1, 2\cdot \left\lceil \frac{k}{2} \right\rceil \cdot W_{1} +\max\left\{0,2\cdot\left(\lef…
Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
Liam Roditty, Ariel Sapir
We present a -APASP algorithm for dense weighted graphs with runtime , where is the weight of an $i^{th}…
A tight negative example for MMS fair allocations
Uriel Feige, Ariel Sapir, Laliv Tauber
We consider the problem of allocating indivisible goods to agents with additive valuation functions. Kurokawa, Procaccia and Wang {[JACM, 2018]} present instances for which every a…
Nonstationary iterative processes
Luba Sapir, Tamara Kogan, Ariel Sapir +1
In this paper we present iterative methods of high efficiency by the criteria of J. F. Traub and A. M. Ostrowski. We define {\it s-nonstationary iterative processes} and prove that…