Online Coloring Co-interval Graphs ∗ (2008)
We study the problem of online coloring co-interval graphs. In this problem, a set of intervals on the real line is presented to the online algorithm in some arbitrary order, and the algorithm must...
An Improved Algorithm for Online Unit Clustering (2008)
Hamid Zarrabi-zadeh, Timothy M. Chan
Abstract. We revisit the online unit clustering problem in one dimension which we recently introduced at WAOA’06: given a sequence of n points on the line, the objective is to partition the points...
A randomized algorithm for online unit clustering (2006)
Timothy M. Chan, Hamid Zarrabi-zadeh
Abstract. In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets...
A randomized algorithm for online unit clustering (2006)
Timothy M. Chan, Hamid Zarrabi-zadeh
Abstract. In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets...
Using Pseudo Approximation Algorithms to Approximate Shortest Paths Above a Terrain (2005)
In this project, we address a general technique for constructing an ε-approximation algorithm out of a so-called pseudo approximation algorithm. We then show how this technique can be applied to the...