Source author record

Kasturi Varadarajan

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Computational Complexity Discrete Mathematics Machine Learning math.PR

Catalog footprint

Research overview

8works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Approximate Clustering via Metric Partitioning

In this paper we consider two metric covering/clustering problems - \textit{Minimum Cost Covering Problem} (MCC) and $k$ -clustering. In the MCC problem, we are given two point sets $X$ (clients) and $Y$ (servers), and a metric on $X \cup Y$ . We would like to cover the clients by balls centered at the servers. The objective function to minimize is the sum of the $α$ -th power of the radii of the balls. Here $α\geq 1$ is a parameter of the problem (but not of a problem instance). MCC is closely related to the $k$ -clustering problem. The main difference between $k$ -clustering and MCC is that in $k$ -clustering one needs to select $k$ balls to cover the clients. For any $\eps > 0$, we describe quasi-polynomial time $(1 + \eps)$ approximation algorithms for both of the problems. However, in case of $k$ -clustering the algorithm uses $(1 + \eps)k$ balls. Prior to our work, a $3^α$ and a ${c}^α$ approximation were achieved by polynomial-time algorithms for MCC and $k$ -clustering, respectively, where $c > 1$ is an absolute constant. These two problems are thus interesting examples of metric covering/clustering problems that admit $(1 + \eps)$-approximation (using $(1+\eps)k$ balls in case of $k$ -clustering), if one is willing to settle for quasi-polynomial time. In contrast, for the variant of MCC where $α$ is part of the input, we show under standard assumptions that no polynomial time algorithm can achieve an approximation factor better than $O(\log |X|)$ for $α\geq \log |X|$ .

preprint2015arXiv

A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment

Given an initial placement of a set of rectangles in the plane, we consider the problem of finding a disjoint placement of the rectangles that minimizes the area of the bounding box and preserves the orthogonal order i.e.\ maintains the sorted ordering of the rectangle centers along both $x$ -axis and $y$ -axis with respect to the initial placement. This problem is known as Layout Adjustment for Disjoint Rectangles(LADR). It was known that LADR is $\mathbb{NP}$ -hard, but only heuristics were known for it. We show that a certain decision version of LADR is $\mathbb{APX}$ -hard, and give a constant factor approximation for LADR.

preprint2015arXiv

On Variants of k-means Clustering

\textit{Clustering problems} often arise in the fields like data mining, machine learning etc. to group a collection of objects into similar groups with respect to a similarity (or dissimilarity) measure. Among the clustering problems, specifically \textit{ $k$ -means} clustering has got much attention from the researchers. Despite the fact that $k$ -means is a very well studied problem its status in the plane is still an open problem. In particular, it is unknown whether it admits a PTAS in the plane. The best known approximation bound in polynomial time is $9+\eps$. In this paper, we consider the following variant of $k$ -means. Given a set $C$ of points in $\mathcal{R}^d$ and a real $f > 0$ , find a finite set $F$ of points in $\mathcal{R}^d$ that minimizes the quantity $f*|F|+\sum_{p\in C} \min_{q \in F} {||p-q||}^2$ . For any fixed dimension $d$ , we design a local search PTAS for this problem. We also give a "bi-criterion" local search algorithm for $k$ -means which uses $(1+\eps)k$ centers and yields a solution whose cost is at most $(1+\eps)$ times the cost of an optimal $k$ -means solution. The algorithm runs in polynomial time for any fixed dimension. The contribution of this paper is two fold. On the one hand, we are being able to handle the square of distances in an elegant manner, which yields near optimal approximation bound. This leads us towards a better understanding of the $k$ -means problem. On the other hand, our analysis of local search might also be useful for other geometric problems. This is important considering that very little is known about the local search method for geometric approximation.

preprint2014arXiv

A Constant-Factor Approximation for Multi-Covering with Disks

We consider variants of the following multi-covering problem with disks. We are given two point sets $Y$ (servers) and $X$ (clients) in the plane, a coverage function $κ:X \rightarrow \mathcal{N}$ , and a constant $α\geq 1$ . Centered at each server is a single disk whose radius we are free to set. The requirement is that each client $x \in X$ be covered by at least $κ(x)$ of the server disks. The objective function we wish to minimize is the sum of the $α$ -th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.

preprint2014arXiv

Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation

We revisit two NP-hard geometric partitioning problems - convex decomposition and surface approximation. Building on recent developments in geometric separators, we present quasi-polynomial time algorithms for these problems with improved approximation guarantees.

preprint2012arXiv

On the Sensitivity of Shape Fitting Problems

In this article, we study shape fitting problems, $ε$ -coresets, and total sensitivity. We focus on the $(j,k)$ -projective clustering problems, including $k$ -median/ $k$ -means, $k$ -line clustering, $j$ -subspace approximation, and the integer $(j,k)$ -projective clustering problem. We derive upper bounds of total sensitivities for these problems, and obtain $ε$ -coresets using these upper bounds. Using a dimension-reduction type argument, we are able to greatly simplify earlier results on total sensitivity for the $k$ -median/ $k$ -means clustering problems, and obtain positively-weighted $ε$ -coresets for several variants of the $(j,k)$ -projective clustering problem. We also extend an earlier result on $ε$ -coresets for the integer $(j,k)$ -projective clustering problem in fixed dimension to the case of high dimension.

preprint2011arXiv

On Isolating Points Using Disks

In this paper, we consider the problem of choosing disks (that we can think of as corresponding to wireless sensors) so that given a set of input points in the plane, there exists no path between any pair of these points that is not intercepted by some disk. We try to achieve this separation using a minimum number of a given set of unit disks. We show that a constant factor approximation to this problem can be found in polynomial time using a greedy algorithm. To the best of our knowledge we are the first to study this optimization problem.

preprint2010arXiv

Algorithms and Hardness for Subspace Approximation

The subspace approximation problem Subspace( $k$ , $p$ ) asks for a $k$ -dimensional linear subspace that fits a given set of points optimally, where the error for fitting is a generalization of the least squares fit and uses the $\ell_{p}$ norm instead. Most of the previous work on subspace approximation has focused on small or constant $k$ and $p$ , using coresets and sampling techniques from computational geometry. In this paper, extending another line of work based on convex relaxation and rounding, we give a polynomial time algorithm, \emph{for any $k$ and any $p \geq 2$ }, with the approximation guarantee roughly $γ_{p} \sqrt{2 - \frac{1}{n-k}}$ , where $γ_{p}$ is the $p$ -th moment of a standard normal random variable N(0,1). We show that the convex relaxation we use has an integrality gap (or "rank gap") of $γ_{p} (1 - ε)$ , for any constant $ε> 0$ . Finally, we show that assuming the Unique Games Conjecture, the subspace approximation problem is hard to approximate within a factor better than $γ_{p} (1 - ε)$ , for any constant $ε> 0$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.