Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:On Flows, Paths, Roots, and Zeros
Speaker:Ruben Becker
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Promotionskolloquium
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Monday, 23 July 2018
Duration:60 Minutes
Building:E1.7 (MMCI)
This thesis has two parts; in the first of which we give new results for various network flow problems. (1) We present a novel dual ascent algorithm for min-cost flow and show that an implementation of it is very efficient on certain instance classes. (2) We approach the problem of numerical stability of interior point network flow algorithms by giving a path following method that works with integer arithmetic solely and is thus guaranteed to be free of any numerical instabilities. (3) We present a gradient descent approach for the undirected transshipment problem and its special case, the single source shortest path problem (SSSP). For distributed computation models this yields the first SSSP-algorithm with near-optimal number of communication rounds.

The second part deals with fundamental topics from algebraic computation. (1) We give an algorithm for computing the complex roots of a complex polynomial. While achieving a comparable bit complexity as previous best results, our algorithm is simple and promising to be of practical impact. It uses a test for counting the roots of a polynomial in a region that is based on Pellet's theorem. (2) We extend this test to polynomial systems, i.e., we develop an algorithm that can certify the existence of a k-fold zero of a zero-dimensional polynomial system within a given region. For bivariate systems, we show experimentally that this approach yields significant improvements when used as inclusion predicate in an elimination method.

Name(s):Ruben Becker
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Ruben Becker, 07/18/2018 03:49 PM
Last modified:
Uwe Brahm/MPII/DE, 07/23/2018 04:01 AM
  • Ruben Becker, 07/18/2018 03:49 PM -- Created document.