101 citations · 211 across the 45 of their papers we have counts for
5 papers · 1 filter
New Approximability Results for the Robust k-Median Problem
Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn +1
We consider a robust variant of the classical -median problem, introduced by Anthony et al. \cite{AnthonyGGN10}. In the \emph{Robust -Median problem}, we are given an -ver…
Computing Real Roots of Real Polynomials
Michael Sagraloff, Kurt Mehlhorn
Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, a…
A Framework for the Verification of Certifying Computations
Eyad Alkassar, Sascha Böhme, Kurt Mehlhorn +1
Formal verification of complex algorithms is challenging. Verifying their implementations goes beyond the state of the art of current automatic verification tools and usually invol…
On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets
Khaled Elbassioni, Kazuhisa Makino, Kurt Mehlhorn +1
Given two bounded convex sets $X\subseteq\RR^m$ and $Y\subseteq\RR^n,$ specified by membership oracles, and a continuous convex-concave function $F:X\times Y\to\RR$, we consider th…
From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition
Kurt Mehlhorn, Michael Sagraloff, Pengming Wang
We present an algorithm for isolating the roots of an arbitrary complex polynomial that also works for polynomials with multiple roots provided that the number of distinct…