Dissertation
Digging deeper into clustering and covering problems
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Spring 2019
DOI: 10.17077/etd.0cx5-cr9b
Abstract
<p>Clustering problems often arise in the fields like data mining, machine learning and computational biology to group a collection of objects into similar groups with respect to a similarity measure. For example, clustering can be used to group genes with related expression patterns. Covering problems are another important class of problems, where the task is to select a subset of objects from a larger set, such that the objects in the subset "cover" (or contain) a given set of elements. Covering problems have found applications in various fields including wireless and sensor networks, VLSI, and image processing. For example, covering can be used to find placement locations of the minimum number of mobile towers to serve all the customers of a region. In this dissertation, we consider an interesting collection of geometric clustering and covering problems, which are modeled as optimization problems. These problems are known to be $\mathsf{NP}$-hard, i.e. no efficient algorithms are expected to be found for these problems that return optimal solutions. Thus, we focus our effort in designing efficient approximation algorithms for these problems that yield near-optimal solutions. In this work, we study three clustering problems: $k$-means, $k$-clustering and Non-Uniform-$k$-center and one covering problem: Metric Capacitated Covering.</p>
<p>$k$-means is one of the most studied clustering problems and probably the most frequently used clustering problem in practical applications. In this problem, we are given a set of points in an Euclidean space and we want to choose $k$ center points from the same Euclidean space. Each input point is assigned to its nearest chosen center, and points assigned to a center form a cluster. The cost per input point is the square of its distance from its nearest center. The total cost is the sum of the costs of the points. The goal is to choose $k$ center points so that the total cost is minimized. We give a local search based algorithm for this problem that always returns a solution of cost within $(1+\eps)$-factor of the optimal cost for any $\eps > 0$. However, our algorithm uses $(1+\eps)k$ center points. The best known approximation before our work was about 9 that uses exactly $k$ centers. The result appears in Chapter \ref{sec:kmeanschap}.</p>
<p>$k$-clustering is another popular clustering problem studied mainly by the theory community. In this problem, each cluster is represented by a ball in the input metric space. We would like to choose $k$ balls whose union contains all the input points. The cost of each ball is its radius to the power $\alpha$ for some given paramater $\alpha \ge 1$. The total cost is the sum of the costs of the chosen $k$ balls. The goal is to find $k$ balls such that the total cost is minimized. We give a probabilistic metric partitioning based algorithm for this problem that always returns a solution of cost within $(1+\eps)$-factor of the optimal cost for any $\eps > 0$. However, our algorithm uses $(1+\eps)k$ balls, and the running time is quasi-polynomial. The best known approximation in polynomial time is $c^{\alpha}$ that uses exactly $k$ balls, where $c$ is a constant. The result appears in Chapter \ref{sec:kcluster}.</p>
<p>Non-Uniform-$k$-center is another clustering problem, which was posed very recently. Like in $k$-clustering here also each cluster is represented by a ball. Additionally, we are given $k$ integers $r_1,\ldots,r_k$, and we want to find the minimum dilation $\alpha$ and choose $k$ balls with radius $\alpha\cdot r_i$ for $1\le i\le k$ whose union contains all the input points. This problem is known to be notoriously hard. No approximation is known even in the special case when $r_i$'s belong to a set of three integers. We give an LP rounding based algorithm for this special case that always returns a solution of cost within a constant factor of the optimal cost. However, our algorithm uses $(2+\eps)k$ balls for some constant $\epsilon$. We also show that this special case can be solved in polynomial time under a practical assumption. Moreover, we prove that the Euclidean version of the problem is also as hard as the general version. These results appear in Chapter \ref{sec:nukc}.</p>
<p>Capacitated Covering is a generalization of the classical set cover problem. In the Metric Capacitated Covering problem, we are given a set of balls and a set of points in a metric space. Additionally, we are given an integer that is referred to as the capacity. The goal is to find a minimum subset of the input set of balls, such that each point can be assigned to the chosen balls in a manner so that the number of points assigned to each ball is bounded by the capacity. We give an LP rounding based algorithm for this problem that always returns a solution of cost within a constant factor of the optimal cost. However, we assume that we are allowed to expand the balls by a fairly small constant. If no expansion is allowed, then the problem is known to not admit any constant approximation. We discuss our findings in Chapter \ref{sec:capa}.</p>
<p>As mentioned above, for many of the problems we consider, we obtain results that improve the best known approximation bounds. Our findings make significant progress towards better understanding the internals of these problems, which have impact across the disciplines. Also, during the course of our work, we have designed tools and techniques, which might be of independent interest for solving similar optimization problems. Finally, in Chapter \ref{sec:conclude}, we conclude our discussion and pose some open questions, which we consider as our potential future work.</p>
Details
- Title: Subtitle
- Digging deeper into clustering and covering problems
- Creators
- Sayan Bandyapadhyay - University of Iowa
- Contributors
- Kasturi Varadarajan (Advisor)Sukumar Ghosh (Committee Member)Suely Oliveira (Committee Member)Sriram Pemmaraju (Committee Member)Xiaodong Wu (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Computer Science
- Date degree season
- Spring 2019
- DOI
- 10.17077/etd.0cx5-cr9b
- Publisher
- University of Iowa
- Number of pages
- xiv, 171 pages
- Copyright
- Copyright © 2019 Sayan Bandyapadhyay
- Language
- English
- Description illustrations
- illustrations (some color)
- Description bibliographic
- Includes bibliographical references (pages 161-171).
- Public Abstract (ETD)
Consider the following two fictitious scenarios. (i) Suppose an organization wants to start a web news portal that will list all the online news articles of the day classified by their categories. However, the articles are assumed to have no category information, and thus here we want to guess the categories of the articles. (ii) Suppose a company has obtained the tender for placing mobile towers in a new city. In the initial plan, it has identified a large set of placement locations such that the towers can serve all the clients in the city. We want to select a “small” number of towers from the plan that still can serve all the clients in the city. We note that the two above mentioned problems belong to the class of clustering problems and the class of covering problems, respectively. Clustering is the task of grouping a set of items into similar groups (or clusters) with respect to a similarity measure. Ideally, items in different groups should have low similarity. Often the items are represented by points in a high dimensional space. The distance between two items represents their similarity. On the other hand, covering is the task of selecting a subset of objects from a larger set, such that the objects in the subset “cover” (or contain) a given set of elements. Ideally, one wants to find such a subset of the minimum size. Usually, the objects and the elements are modeled using geometric shapes and points, respectively. We have considered several clustering and covering problems in this thesis, and have designed improved algorithms for solving them. Our main contribution is to prove theoretical guarantees on the quality of the solutions produced by our algorithms.
- Academic Unit
- Computer Science
- Record Identifier
- 9983777193702771
Metrics
426 File views/ downloads
468 Record Views