BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We give an O∗(1.0821n)-time, polynomial space algorithm for computing Maximum Independent Set in graphs with bounded degree 3. This improves all the previous running time bounds known for the problem.
The Metric k-median problem over a metric space (X,d) is defined as follows: given a set L⊆X of facility locations and a set C⊆X of clients, open a set F⊆L of k facilities such that the total service cost, defined as Φ(F,C)≡∑x∈Cminf∈Fd(x,f), is minimised. The metric k-means problem is defined similarly using squared distances. In many applications there are additional constraints that any solution needs to satisfy. This gives rise to different constrained versions of the problem such as r-gather, fault-tolerant, outlier k-means/k-median problem. Surprisingly, for many of these constrained problems, no constant-approximation algorithm is known. We give FPT algorithms with constant approximation guarantee for a range of constrained k-median/means problems. For some of the constrained problems, ours is the first constant factor approximation algorithm whereas for others, we improve or match the approximation guarantee of previous works. We work within the unified framework of Ding and Xu that allows us to simultaneously obtain algorithms for a range of constrained problems. In particular, we obtain a (3+ε)-approximation and (9+ε)-approximation for the constrained versions of the k-median and k-means problem respectively in FPT time. In many practical settings of the k-median/means problem, one is allowed to open a facility at any client location, i.e., C⊆L. For this special case, our algorithm gives a (2+ε)-approximation and (4+ε)-approximation for the constrained versions of k-median and k-means problem respectively in FPT time. Since our algorithm is based on simple sampling technique, it can also be converted to a constant-pass log-space streaming algorithm.
We generalise the results of Bhattacharya et al. (Journal of Computing Systems, 62(1):93-115, 2018) for the list-k-means problem defined as -- for a (unknown) partition X1,...,Xk of the dataset X⊆Rd, find a list of k-center sets (each element in the list is a set of k centers) such that at least one of k-center sets {c1,...,ck} in the list gives an (1+ε)-approximation with respect to the cost function minpermutation π[∑i=1k∑x∈Xi∣∣x−cπ(i)∣∣2]. The list-k-means problem is important for the constrained k-means problem since algorithms for the former can be converted to PTAS for various versions of the latter. Following are the consequences of our generalisations: - Streaming algorithm: Our D2-sampling based algorithm running in a single iteration allows us to design a 2-pass, logspace streaming algorithm for the list-k-means problem. This can be converted to a 4-pass, logspace streaming PTAS for various constrained versions of the k-means problem. - Faster PTAS under stability: Our generalisation is also useful in k-means clustering scenarios where finding good centers becomes easy once good centers for a few "bad" clusters have been chosen. One such scenario is clustering under stability where the number of such bad clusters is a constant. Using the above idea, we significantly improve the running time of the known algorithm from O(dn3)(klogn)poly(β1,ε1) to O(dn3kO~βε(βε1)).
The classical center based clustering problems such as k-means/median/center assume that the optimal clusters satisfy the locality property that the points in the same cluster are close to each other. A number of clustering problems arise in machine learning where the optimal clusters do not follow such a locality property. Consider a variant of the k-means problem that may be regarded as a general version of such problems. Here, the optimal clusters O1,...,Ok are an arbitrary partition of the dataset and the goal is to output k-centers c1,...,ck such that the objective function ∑i=1k∑x∈Oi∣∣x−ci∣∣2 is minimized. It is not difficult to argue that any algorithm (without knowing the optimal clusters) that outputs a single set of k centers, will not behave well as far as optimizing the above objective function is concerned. However, this does not rule out the existence of algorithms that output a list of such k centers such that at least one of these k centers behaves well. Given an error parameter ε>0, let ℓ denote the size of the smallest list of k-centers such that at least one of the k-centers gives a (1+ε) approximation w.r.t. the objective function above. In this paper, we show an upper bound on ℓ by giving a randomized algorithm that outputs a list of 2O~(k/ε) k-centers. We also give a closely matching lower bound of 2Ω~(k/ε). Moreover, our algorithm runs in time O(nd⋅2O~(k/ε)). This is a significant improvement over the previous result of Ding and Xu who gave an algorithm with running time O(nd⋅(logn)k⋅2poly(k/ε)) and output a list of size O((logn)k⋅2poly(k/ε)).
Space efficient algorithms play a central role in dealing with large amount of data. In such settings, one would like to analyse the large data using small amount of "working space". One of the key steps in many algorithms for analysing large data is to maintain a (or a small number) random sample from the data points. In this paper, we consider two space restricted settings -- (i) streaming model, where data arrives over time and one can use only a small amount of storage, and (ii) query model, where we can structure the data in low space and answer sampling queries. In this paper, we prove the following results in above two settings: - In the streaming setting, we would like to maintain a random sample from the elements seen so far. We prove that one can maintain a random sample using O(logn) random bits and O(logn) space, where n is the number of elements seen so far. We can extend this to the case when elements have weights as well. - In the query model, there are n elements with weights w1,...,wn (which are w-bit integers) and one would like to sample a random element with probability proportional to its weight. Bringmann and Larsen (STOC 2013) showed how to sample such an element using nw+1 space (whereas, the information theoretic lower bound is nw). We consider the approximate sampling problem, where we are given an error parameter ε, and the sampling probability of an element can be off by an ε factor. We give matching upper and lower bounds for this problem.
The k-means++ seeding algorithm is one of the most popular algorithms that is used for finding the initial k centers when using the k-means heuristic. The algorithm is a simple sampling procedure and can be described as follows: Pick the first center randomly from the given points. For i>1, pick a point to be the ith center with probability proportional to the square of the Euclidean distance of this point to the closest previously (i−1) chosen centers. The k-means++ seeding algorithm is not only simple and fast but also gives an O(logk) approximation in expectation as shown by Arthur and Vassilvitskii. There are datasets on which this seeding algorithm gives an approximation factor of Ω(logk) in expectation. However, it is not clear from these results if the algorithm achieves good approximation factor with reasonably high probability (say 1/poly(k)). Brunsch and Röglin gave a dataset where the k-means++ seeding algorithm achieves an O(logk) approximation ratio with probability that is exponentially small in k. However, this and all other known lower-bound examples are high dimensional. So, an open problem was to understand the behavior of the algorithm on low dimensional datasets. In this work, we give a simple two dimensional dataset on which the seeding algorithm achieves an O(logk) approximation ratio with probability exponentially small in k. This solves open problems posed by Mahajan et al. and by Brunsch and Röglin.
We give an improved analysis of the simple D2-sampling based PTAS for the k-means clustering problem given by Jaiswal, Kumar, and Sen (Algorithmica, 2013). The improvement on the running time is from O(nd⋅2O~(k2/ε)) to O(nd⋅2O~(k/ε)).
The k-means++ seeding algorithm is one of the most popular algorithms that is used for finding the initial k centers when using the k-means heuristic. The algorithm is a simple sampling procedure and can be described as follows: {quote} Pick the first center randomly from among the given points. For i>1, pick a point to be the ith center with probability proportional to the square of the Euclidean distance of this point to the previously (i−1) chosen centers. {quote} The k-means++ seeding algorithm is not only simple and fast but gives an O(logk) approximation in expectation as shown by Arthur and Vassilvitskii \cite{av07}. There are datasets \cite{av07,adk09} on which this seeding algorithm gives an approximation factor Ω(logk) in expectation. However, it is not clear from these results if the algorithm achieves good approximation factor with reasonably large probability (say 1/poly(k)). Brunsch and Röglin \cite{br11} gave a dataset where the k-means++ seeding algorithm achieves an approximation ratio of (2/3−ε)⋅logk only with probability that is exponentially small in k. However, this and all other known {\em lower-bound examples} \cite{av07,adk09} are high dimensional. So, an open problem is to understand the behavior of the algorithm on low dimensional datasets. In this work, we give a simple two dimensional dataset on which the seeding algorithm achieves an approximation ratio c (for some universal constant c) only with probability exponentially small in k. This is the first step towards solving open problems posed by Mahajan et al \cite{mnv12} and by Brunsch and Röglin \cite{br11}.
Given a set of points P⊂Rd, the k-means clustering problem is to find a set of k {\em centers} C={c1,...,ck},ci∈Rd, such that the objective function ∑x∈Pd(x,C)2, where d(x,C) denotes the distance between x and the closest center in C, is minimized. This is one of the most prominent objective functions that have been studied with respect to clustering. D2-sampling \cite{ArthurV07} is a simple non-uniform sampling technique for choosing points from a set of points. It works as follows: given a set of points P⊆Rd, the first point is chosen uniformly at random from P. Subsequently, a point from P is chosen as the next sample with probability proportional to the square of the distance of this point to the nearest previously sampled points. D2-sampling has been shown to have nice properties with respect to the k-means clustering problem. Arthur and Vassilvitskii \cite{ArthurV07} show that k points chosen as centers from P using D2-sampling gives an O(logk) approximation in expectation. Ailon et. al. \cite{AJMonteleoni09} and Aggarwal et. al. \cite{AggarwalDK09} extended results of \cite{ArthurV07} to show that O(k) points chosen as centers using D2-sampling give O(1) approximation to the k-means objective function with high probability. In this paper, we further demonstrate the power of D2-sampling by giving a simple randomized (1+ε)-approximation algorithm that uses the D2-sampling in its core.
Bourgain showed that any noise stable Boolean function f can be well-approximated by a junta. In this note we give an exponential sharpening of the parameters of Bourgain's result under the additional assumption that f is a halfspace.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.