Algorithms and Theory

We provide a general design framework for dynamic mechanisms under complex environments, coined Lossless History Compression mechanisms. Lossless history compression mechanisms compress the history into a state carrying the least historical information without losing any generality in terms of either revenue or welfare. In particular, the characterization works for almost arbitrary constraints...

We present a new local-search algorithm for the k-median clustering problem. We show that local optima for this algorithm give an (2.836+eps)-approximation; our result improves upon the (3+eps)-approximate local-search algorithm of Arya et al. (2001). Moreover, a computer-aided analysis of a natural extension suggests that this approach may lead to a improvement over the best-known...

The (non-uniform) sparsest cut problem is the following classical graph-partitioning problem: given a ``supply'' graph, and demands on pairs of vertices, delete some subset of supply edges to minimize the ratio of the supply edges cut to the total demand of the pairs separated by this deletion. The sparsest cut problem has been a driver for new algorithmic approaches. Despite much effort, there...

We consider the numerical taxonomy problem of fitting a positive distance function $\calD:{S\choose 2}\rightarrow \mathbb R_{>0}$ by a tree metric. We want a tree $T$ with positive edge weights and including $S$ among the vertices so that their distances in $T$ match those in $\calD$. A nice application is in evolutionary biology where the tree $T$ aims to approximate the branching process...