5 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}…
Dependency Preservation May Prevent Stopping at
Amir Sapir, Ariel Sapir
Traditionally, it was accepted that a relational database can be normalized step-by-step, from a set of un-normalized tables to tables in , then to , then to , then…
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…