101 citations · 211 across the 45 of their papers we have counts for
28 papers · 1 filter
Improving Order with Queues
Andreas Karrenbauer, Kurt Mehlhorn, Pranabendu Misra +4
Given a sequence of numbers and parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that queues suffice to sort…
Physarum Inspired Dynamics to Solve Semi-Definite Programs
Yuan Gao, Hamidreza Kamkari, Andreas Karrenbauer +2
Physarum Polycephalum is a slime mold that can solve shortest path problems. A mathematical model based on Physarum's behavior, known as the Physarum Directed Dynamics, can solve p…
Physarum-Inspired Multi-Commodity Flow Dynamics
Vincenzo Bonifaci, Enrico Facca, Frederic Folz +6
In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks. For the shortest path pr…
Trustworthy Graph Algorithms
Mohammad Abdulaziz, Kurt Mehlhorn, Tobias Nipkow
The goal of the LEDA project was to build an easy-to-use and extendable library of correct and efficient data structures, graph algorithms and geometric algorithms. We report on th…
Ratio-Balanced Maximum Flows
Hannaneh Akrami, Kurt Mehlhorn, Tommy Odland
When a loan is approved for a person or company, the bank is subject to \emph{credit risk}; the risk that the lender defaults. To mitigate this risk, a bank will require some form…
Convergence of the Non-Uniform Physarum Dynamics
Andreas Karrenbauer, Pavel Kolev, Kurt Mehlhorn
Let , , and . We show under fairly general conditions that the non-uniform Physarum dynamics \[ \dot{x}_…
The Query Complexity of a Permutation-Based Variant of Mastermind
Peyman Afshani, Manindra Agrawal, Benjamin Doerr +3
We study the query complexity of a permutation-based variant of the guessing game Mastermind. In this variant, the secret is a pair which consists of a binary string $z \in…
Multi-finger binary search trees
Parinya Chalermsook, Mayank Goswami, László Kozma +2
We study multi-finger binary search trees (BSTs), a far-reaching extension of the classical BST model, with connections to the well-studied -server problem. Finger search is a p…
On testing substitutability
Cosmina Croitoru, Kurt Mehlhorn
The papers~\cite{hatfimmokomi11} and~\cite{azizbrilharr13} propose algorithms for testing whether the choice function induced by a (strict) preference list of length over a uni…
On Fair Division of Indivisible Items
Bhaskar Chaudhury, Yun Kuen Cheung, Jugal Garg +3
We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric…
Two Results on Slime Mold Computations
Ruben Becker, Vincenzo Bonifaci, Andreas Karrenbauer +2
We present two results on slime mold computations. In wet-lab experiments (Nature'00) by Nakagaki et al. the slime mold Physarum polycephalum demonstrated its ability to solve shor…
Satiation in Fisher Markets and Approximation of Nash Social Welfare
Jugal Garg, Martin Hoefer, Kurt Mehlhorn
We study linear Fisher markets with satiation. In these markets, sellers have earning limits and buyers have utility limits. Beyond natural applications in economics, these markets…
Engineering DFS-Based Graph Algorithms
Kurt Mehlhorn, Stefan Näher, Peter Sanders
Depth-first search (DFS) is the basis for many efficient graph algorithms. We introduce general techniques for the efficient implementation of DFS-based graph algorithms and exempl…
An Integer Interior Point Method for Min-Cost Flow Using Arc Contractions and Deletions
Ruben Becker, Andreas Karrenbauer, Kurt Mehlhorn
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 meth…
The landscape of bounds for binary search trees
Parinya Chalermsook, Mayank Goswami, László Kozma +2
Binary search trees (BSTs) with rotations can adapt to various kinds of structure in search sequences, achieving amortized access times substantially better than the Theta(log n) w…
Improved Balanced Flow Computation Using Parametric Flow
Omar Darwish, Kurt Mehlhorn
We present a new algorithm for computing balanced flows in equality networks arising in market equilibrium computations. The current best time bound for computing balanced flows in…
An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
Rann Duan, Jugal Garg, Kurt Mehlhorn
We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear Arrow-Debreu model. For a market with agents and integral utilities bound…
A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming
Kurt Mehlhorn, Sanjeev Saxena
Linear programming is now included in algorithm undergraduate and postgraduate courses for computer science majors. We give a self-contained treatment of an interior-point method w…
Pattern-avoiding access in binary search trees
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST…
Greedy Is an Almost Optimal Deque
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Patrascu (DHIKP) to accommodate for insertions and deletions. Within this…
Self-Adjusting Binary Search Trees: What Makes Them Tick?
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
Splay trees (Sleator and Tarjan) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs)…
Still Simpler Way of Introducing Interior-Point method for Linear Programming
Sanjeev Saxena
Linear Programming is now included in Algorithm undergraduate and postgraduate courses for Computer Science majors. It is possible to teach interior-point methods directly with jus…
Cache-Oblivious VAT-Algorithms
Tomasz Jurkiewicz, Kurt Mehlhorn, Patrick Nicholson
The VAT-model (virtual address translation model) extends the EM-model (external memory model) and takes the cost of address translation in virtual memories into account. In this m…
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…