101 citations · 211 across the 45 of their papers we have counts for
8 papers · 1 filter
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…
Approximate Spectral Clustering: Efficiency and Guarantees
Pavel Kolev, Kurt Mehlhorn
Approximate Spectral Clustering (ASC) is a popular and successful heuristic for partitioning the nodes of a graph into clusters for which the ratio of outside connections compa…
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…