We review the recent progress in the design of efficient algorithms for various problems in
geometric optimization. We present several techniques used to attack these problems, such …

This article shows how to solve linear programs of the form min Ax= b, x≥ 0 c⊤ x with n
variables in time O*((n ω+ n 2.5− α/2+ n 2+ 1/6) log (n/δ)), where ω is the exponent of matrix …

The goal of this textbook is twofold. First, the book serves as an introduction to the field of
parameterized algorithms and complexity accessible to graduate students and advanced …

This well-accepted introduction to computational geometry is a textbook for high-level
undergraduate and low-level graduate courses. The focus is on algorithms and hence the …

Interior point algorithms for solving linear programs have been studied extensively for a long
time [eg Karmarkar 1984; Lee, Sidford FOCS'14; Cohen, Lee, Song STOC'19]. For linear …

Algorithms in varied fields use the idea of maintaining a distribution over a certain set and
use the multiplicative update rule to iteratively change these weights. Their analyses are …

A simple randomized algorithm is developed which computes the smallest enclosing disk of
a finite set of points in the plane in expected linear time. The algorithm is based on Seidel's …

Random sampling is used for several new geometric algorithms. The algorithms are “Las
Vegas,” and their expected bounds are with respect to the random behavior of the …

We give a deterministic polynomial time method for finding a set cover in a set system (X, ℜ)
of VC-dimension d such that the size of our cover is at most a factor of O (d log (dc)) from the …

We explore random sampling as a tool for solving undirected graph problems. We show that
the sparse graph, or skeleton, which arises when we randomly sample a graph's edges will …