Source author record

Ruben Becker

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.NA Computer Science and Game Theory math.OC Numerical Analysis Symbolic Computation

Catalog footprint

Research overview

5works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

We present a method for solving the transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of $1 + \varepsilon$ in undirected graphs with non-negative edge weights using a tailored gradient descent algorithm. Using $\tilde{O}(\cdot)$ to hide polylogarithmic factors in $n$ (the number of nodes in the graph), our gradient descent algorithm takes $\tilde O(\varepsilon^{-2})$ iterations, and in each iteration it solves an instance of the transshipment problem up to a multiplicative error of $\operatorname{polylog} n$ . In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a randomized rounding scheme, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve upon prior work by obtaining the following results: (1) Broadcast CONGEST model: $(1 + \varepsilon)$ -approximate SSSP using $\tilde{O}((\sqrt{n} + D)\varepsilon^{-3})$ rounds, where $D$ is the (hop) diameter of the network. (2) Broadcast congested clique model: $(1 + \varepsilon)$ -approximate transshipment and SSSP using $\tilde{O}(\varepsilon^{-2})$ rounds. (3) Multipass streaming model: $(1 + \varepsilon)$ -approximate transshipment and SSSP using $\tilde{O}(n)$ space and $\tilde{O}(\varepsilon^{-2})$ passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative edge weights that are polynomially bounded in $n$ ; for general non-negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights.

preprint2020arXiv

Maximizing Influence-based Group Shapley Centrality

One key problem in network analysis is the so-called influence maximization problem, which consists in finding a set $S$ of at most $k$ seed users, in a social network, maximizing the spread of information from $S$ . This paper studies a related but slightly different problem: We want to find a set $S$ of at most $k$ seed users that maximizes the spread of information, when $S$ is added to an already pre-existing - but unknown - set of seed users $T$ . We consider such scenario to be very realistic. Assume a central entity wants to spread a piece of news, while having a budget to influence $k$ users. This central authority may know that some users are already aware of the information and are going to spread it anyhow. The identity of these users being however completely unknown. We model this optimization problem using the Group Shapley value, a well-founded concept from cooperative game theory. While the standard influence maximization problem is easy to approximate within a factor $1-1/e-ε$ for any $ε>0$ , assuming common computational complexity conjectures, we obtain strong hardness of approximation results for the problem at hand in this paper. Maybe most prominently, we show that it cannot be approximated within $1/n^{o(1)}$ under the Gap Exponential Time Hypothesis. Hence, it is unlikely to achieve anything better than a polynomial factor approximation. Nevertheless, we show that a greedy algorithm can achieve a factor of $\frac{1-1/e}{k}-ε$ for any $ε>0$ , showing that not all is lost in settings where $k$ is bounded.

preprint2016arXiv

A Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration

We describe a subdivision algorithm for isolating the complex roots of a polynomial $F\in\mathbb{C}[x]$ . Given an oracle that provides approximations of each of the coefficients of $F$ to any absolute error bound and given an arbitrary square $\mathcal{B}$ in the complex plane containing only simple roots of $F$ , our algorithm returns disjoint isolating disks for the roots of $F$ in $\mathcal{B}$ . Our complexity analysis bounds the absolute error to which the coefficients of $F$ have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square $\mathcal{B}$ , namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the \emph{benchmark problem}, namely, to isolate all the roots of a polynomial of degree $n$ with integer coefficients of bit size less than $τ$ , our algorithm needs $\tilde O(n^3+n^2τ)$ bit operations, which is comparable to the record bound of Pan (2002). It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a "soft-test" to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm.

preprint2016arXiv

An Integer Interior Point Method for Min-Cost Flow Using Arc Contractions and Deletions

We present an interior point method for the min-cost flow problem that uses arc contractions and deletions to steer clear from the boundary of the polytope when path-following methods come too close. We obtain a randomized algorithm running in expected $\tilde O( m^{3/2} )$ time that only visits integer lattice points in the vicinity of the central path of the polytope. This enables us to use integer arithmetic like classical combinatorial algorithms typically do. We provide explicit bounds on the size of the numbers that appear during all computations. By presenting an integer arithmetic interior point algorithm we avoid the tediousness of floating point error analysis and achieve a method that is guaranteed to be free of any numerical issues. We thereby eliminate one of the drawbacks of numerical methods in contrast to combinatorial min-cost flow algorithms that still yield the most efficient implementations in practice, despite their inferior worst-case time complexity.

preprint2014arXiv

A Combinatorial $\tilde{O}(m^{3/2})$ -time Algorithm for the Min-Cost Flow Problem

We present a combinatorial method for the min-cost flow problem and prove that its expected running time is bounded by $\tilde O(m^{3/2})$ . This matches the best known bounds, which previously have only been achieved by numerical algorithms or for special cases. Our contribution contains three parts that might be interesting in their own right: (1) We provide a construction of an equivalent auxiliary network and interior primal and dual points with potential $P_0=\tilde{O}(\sqrt{m})$ in linear time. (2) We present a combinatorial potential reduction algorithm that transforms initial solutions of potential $P_0$ to ones with duality gap below $1$ in $\tilde O(P_0\cdot \mbox{CEF}(n,m,ε))$ time, where $ε^{-1}=O(m^2)$ and $\mbox{CEF}(n,m,ε)$ denotes the running time of any combinatorial algorithm that computes an $ε$ -approximate electrical flow. (3) We show that solutions with duality gap less than $1$ suffice to compute optimal integral potentials in $O(m+n\log n)$ time with our novel crossover procedure. All in all, using a variant of a state-of-the-art $ε$ -electrical flow solver, we obtain an algorithm for the min-cost flow problem running in $\tilde O(m^{3/2})$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ruben Becker

Research overview

Is this your work?

5 publications

Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

Maximizing Influence-based Group Shapley Centrality

A Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration

An Integer Interior Point Method for Min-Cost Flow Using Arc Contractions and Deletions

A Combinatorial $\tilde{O}(m^{3/2})$ -time Algorithm for the Min-Cost Flow Problem

See the researcher in context

Building this map preview

Ruben Becker

Research overview

Is this your work?

5 publications

Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

Maximizing Influence-based Group Shapley Centrality

A Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration

An Integer Interior Point Method for Min-Cost Flow Using Arc Contractions and Deletions

A Combinatorial O~(m3/2)\tilde{O}(m^{3/2})O~(m3/2)-time Algorithm for the Min-Cost Flow Problem

See the researcher in context

Building this map preview

A Combinatorial $\tilde{O}(m^{3/2})$ -time Algorithm for the Min-Cost Flow Problem