Given two sets $S$ and $T$ of points in the plane, of total size $n$, a {many-to-many} matching between $S$ and $T$ is a set of pairs $(p,q)$ such that $pin S$, $qin T$ and for each $rin Scup T$, $r$ appears in at least one such pair. The {cost of a
pair} $(p,q)$ is the (Euclidean) distance between $p$ and $q$. In the {minimum-cost many-to-many matching} problem, the goal is to compute a many-to-many matching such that the sum of the costs of the pairs is minimized. This problem is a restricted version of minimum-weight edge cover in a bipartite graph, and hence can be solved in $O(n^3)$ time. In a more restricted setting where all the points are on a line, the problem can be solved in $O(nlog n)$ time [Colannino, Damian, Hurtado, Langerman, Meijer, Ramaswami, Souvaine, Toussaint; Graphs Comb., 2007]. However, no progress has been made in the general planar case in improving the cubic time bound. In this paper, we obtain an $O(n^2cdot poly(log n))$ time exact algorithm and an $O( n^{3/2}cdot poly(log n))$ time $(1+epsilon)$-approximation in the planar case. Our results affirmatively address an open problem posed in [Colannino et al., Graphs Comb., 2007].
In this paper, we consider the Minimum-Load $k$-Clustering/Facility Location (MLkC) problem where we are given a set $P$ of $n$ points in a metric space that we have to cluster and an integer $k$ that denotes the number of clusters. Additionally, we
are given a set $F$ of cluster centers in the same metric space. The goal is to select a set $Csubseteq F$ of $k$ centers and assign each point in $P$ to a center in $C$, such that the maximum load over all centers is minimized. Here the load of a center is the sum of the distances between it and the points assigned to it. Although clustering/facility location problems have a rich literature, the minimum-load objective is not studied substantially, and hence MLkC has remained a poorly understood problem. More interestingly, the problem is notoriously hard even in some special cases including the one in line metrics as shown by Ahmadian et al. [ACM Trans. Algo. 2018]. They also show APX-hardness of the problem in the plane. On the other hand, the best-known approximation factor for MLkC is $O(k)$, even in the plane. In this work, we study a fair version of MLkC inspired by the work of Chierichetti et al. [NeurIPS, 2017], which generalizes MLkC. Here the input points are colored by one of the $ell$ colors denoting the group they belong to. MLkC is the special case with $ell=1$. Considering this problem, we are able to obtain a $3$-approximation in $f(k,ell)cdot n^{O(1)}$ time. Also, our scheme leads to an improved $(1 + epsilon)$-approximation in case of Euclidean norm, and in this case, the running time depends only polynomially on the dimension $d$. Our results imply the same approximations for MLkC with running time $f(k)cdot n^{O(1)}$, achieving the first constant approximations for this problem in general and Euclidean metric spaces.
In this paper, we study the lower- and upper-bounded covering (LUC) problem, where we are given a set $P$ of $n$ points, a collection $mathcal{B}$ of balls, and parameters $L$ and $U$. The goal is to find a minimum-sized subset $mathcal{B}subseteq ma
thcal{B}$ and an assignment of the points in $P$ to $mathcal{B}$, such that each point $pin P$ is assigned to a ball that contains $p$ and for each ball $B_iin mathcal{B}$, at least $L$ and at most $U$ points are assigned to $B_i$. We obtain an LP rounding based constant approximation for LUC by violating the lower and upper bound constraints by small constant factors and expanding the balls by again a small constant factor. Similar results were known before for covering problems with only the upper bound constraint. We also show that with only the lower bound constraint, the above result can be obtained without any lower bound violation. Covering problems have close connections with facility location problems. We note that the known constant-approximation for the corresponding lower- and upper-bounded facility location problem, violates the lower and upper bound constraints by a constant factor.
In the Metric Capacitated Covering (MCC) problem, given a set of balls $mathcal{B}$ in a metric space $P$ with metric $d$ and a capacity parameter $U$, the goal is to find a minimum sized subset $mathcal{B}subseteq mathcal{B}$ and an assignment of th
e points in $P$ to the balls in $mathcal{B}$ such that each point is assigned to a ball that contains it and each ball is assigned with at most $U$ points. MCC achieves an $O(log |P|)$-approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of $o(log |P|)$ even with $beta < 3$ factor expansion of the balls. Bandyapadhyay~{et al.} [SoCG 2018, DCG 2019] showed that one can obtain an $O(1)$-approximation for the problem with $6.47$ factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound $3$ and the upper bound $6.47$. In this current work, we show that it is possible to obtain an $O(1)$-approximation with only $4.24$ factor expansion of the balls. We also show a similar upper bound of $5$ for a more generalized version of MCC for which the best previously known bound was $9$.
The Non-Uniform $k$-center (NUkC) problem has recently been formulated by Chakrabarty, Goyal and Krishnaswamy [ICALP, 2016] as a generalization of the classical $k$-center clustering problem. In NUkC, given a set of $n$ points $P$ in a metric space a
nd non-negative numbers $r_1, r_2, ldots , r_k$, the goal is to find the minimum dilation $alpha$ and to choose $k$ balls centered at the points of $P$ with radius $alphacdot r_i$ for $1le ile k$, such that all points of $P$ are contained in the union of the chosen balls. They showed that the problem is NP-hard to approximate within any factor even in tree metrics. On the other hand, they designed a bi-criteria constant approximation algorithm that uses a constant times $k$ balls. Surprisingly, no true approximation is known even in the special case when the $r_i$s belong to a fixed set of size 3. In this paper, we study the NUkC problem under perturbation resilience, which was introduced by Bilu and Linial [Combinatorics, Probability and Computing, 2012]. We show that the problem under 2-perturbation resilience is polynomial time solvable when the $r_i$s belong to a constant sized set. However, we show that perturbation resilience does not help in the general case. In particular, our findings imply that even with perturbation resilience one cannot hope to find any good approximation for the problem.
We study four classical graph problems -- Hamiltonian path, Traveling salesman, Minimum spanning tree, and Minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points i
n the Euclidean plane, and many of them are NP-hard. In this work, we consider these problems in two restricted settings: (i) collinear points and (ii) equidistant points on a circle. We show that almost all of these problems can be solved in linear time in these constrained, yet non-trivial settings.
In this article, we consider a collection of geometric problems involving points colored by two colors (red and blue), referred to as bichromatic problems. The motivation behind studying these problems is two fold; (i) these problems appear naturally
and frequently in the fields like Machine learning, Data mining, and so on, and (ii) we are interested in extending the algorithms and techniques for single point set (monochromatic) problems to bichromatic case. For all the problems considered in this paper, we design low polynomial time exact algorithms. These algorithms are based on novel techniques which might be of independent interest.
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 te
xtit{$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_{pin 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.
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 l
ike to cover the clients by balls centered at the servers. The objective function to minimize is the sum of the $alpha$-th power of the radii of the balls. Here $alpha 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^{alpha}$ and a ${c}^{alpha}$ 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 $alpha$ 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 $alpha geq log |X|$.
textit{Voronoi game} is a geometric model of competitive facility location problem played between two players. Users are generally modeled as points uniformly distributed on a given underlying space. Each player chooses a set of points in the underly
ing space to place their facilities. Each user avails service from its nearest facility. Service zone of a facility consists of the set of users which are closer to it than any other facility. Payoff of each player is defined by the quantity of users served by all of its facilities. The objective of each player is to maximize their respective payoff. In this paper we consider the two players {it Voronoi game} where the underlying space is a road network modeled by a graph. In this framework we consider the problem of finding $k$ optimal facility locations of Player 2 given any placement of $m$ facilities by Player 1. Our main result is a dynamic programming based polynomial time algorithm for this problem on tree network. On the other hand, we show that the problem is strongly $mathcal{NP}$-complete for graphs. This proves that finding a winning strategy of P2 is $mathcal{NP}$-complete. Consequently, we design an $1-frac{1}{e}$ factor approximation algorithm, where $e approx 2.718$.
