We study the classic (Uncapacitated) Facility Location problem on Unit Disk Graphs (UDGs). For a given point set P in the plane, the unit disk graph UDG(P) on P has vertex set P and an edge between two distinct points p, q ∈ P if and only if their Euclidean distance |pq| is at most 1. The weight of the edge pq is equal to their distance |pq|. An instance of {Facility Location} on UDG(P) consists of a set C ⊆ P of clients and a set F ⊆ P of facilities, each having an opening cost f_i. The goal is to pick a subset F' ⊆ F to open while minimizing ∑_{i ∈ F'} f_i + ∑_{v ∈ C} d(v,F'), where d(v,F') is the distance of v to nearest facility in F' through UDG(P). In this paper, we present the first Quasi-Polynomial Time Approximation Schemes (QPTAS) for the problem. While approximation schemes are well-established for facility location problems on sparse geometric graphs (such as planar graphs), there is a lack of such results for dense graphs. Specifically, prior to this study, to the best of our knowledge, there was no approximation scheme for any facility location problem on UDGs in the general setting.

In this paper, we present approximation algorithms for the airport and railway problem (AR) on several classes of graphs. The AR problem, introduced by [Anna Adamaszek et al., 2016], is a combination of the Capacitated Facility Location problem (CFL) and the network design problem. An AR instance consists of a set of points (cities) V in a metric d(.,.), each of which is associated with a non-negative cost f_v and a number k, which represent respectively the cost of establishing an airport (facility) in the corresponding point, and the universal airport capacity. A feasible solution is a network of airports and railways providing services to all cities without violating any capacity, where railways are edges connecting pairs of points, with their costs equivalent to the distance between the respective points. The objective is to find such a network with the least cost. In other words, find a forest, each component having at most k points and one open facility, minimizing the total cost of edges and airport opening costs. Adamaszek et al. [Anna Adamaszek et al., 2016] presented a PTAS for AR in the two-dimensional Euclidean metric ℝ² with a uniform opening cost. In subsequent work [Anna Adamaszek et al., 2018] presented a bicriteria 4/3 (2+1/α)-approximation algorithm for AR with non-uniform opening costs but violating the airport capacity by a factor of 1+α, i.e. (1+α)k capacity where 0 < α ≤ 1, a (2+k/(k-1)+ε)-approximation algorithm and a bicriteria Quasi-Polynomial Time Approximation Scheme (QPTAS) for the same problem in the Euclidean plane ℝ². In this work, we give a 2-approximation for AR with a uniform opening cost for general metrics and an O(log n)-approximation for non-uniform opening costs. We also give a QPTAS for AR with a uniform opening cost in graphs of bounded treewidth and a QPTAS for a slightly relaxed version in the non-uniform setting. The latter implies O(1)-approximation on graphs of bounded doubling dimensions, graphs of bounded highway dimensions and planar graphs in quasi-polynomial time.

Clustering problems are well studied in a variety of fields, such as data science, operations research, and computer science. Such problems include variants of center location problems, k -median and k -means to name a few. In some cases, not all data points need to be clustered; some may be discarded for various reasons. For instance, some points may arise from noise in a dataset or one might be willing to discard a certain fraction of the points to avoid incurring unnecessary overhead in the cost of a clustering solution. We study clustering problems with outliers. More specifically, we look at uncapacitated facility location (UFL), k - median , and k - means . In these problems, we are given a set X of data points in a metric space δ(., .), a set C of possible centers (each maybe with an opening cost), maybe an integer parameter k , plus an additional parameter z as the number of outliers. In uncapacitated facility location with outliers, we have to open some centers, discard up to z points of X , and assign every other point to the nearest open center, minimizing the total assignment cost plus center opening costs. In k - median and k - means , we have to open up to k centers, but there are no opening costs. In k - means , the cost of assigning j to i is δ 2 ( j , i ). We present several results. Our main focus is on cases where δ is a doubling metric (this includes fixed dimensional Euclidean metrics as a special case) or is the shortest path metrics of graphs from a minor-closed family of graphs. For uniform-cost UFL with outliers on such metrics, we show that a multiswap simple local search heuristic yields a PTAS. With a bit more work, we extend this to bicriteria approximations for the k - median and k - means problems in the same metrics where, for any constant ϵ > 0, we can find a solution using (1 + ϵ) k centers whose cost is at most a (1 + ϵ)-factor of the optimum and uses at most z outliers. Our algorithms are all based on natural multiswap local search heuristics. We also show that natural local search heuristics that do not violate the number of clusters and outliers for k - median (or k - means ) will have unbounded gap even in Euclidean metrics. Furthermore, we show how our analysis can be extended to general metrics for k - means with outliers to obtain a (25 + ϵ, 1 + ϵ)-approximation: an algorithm that uses at most (1 + ϵ) k clusters and whose cost is at most 25 + ϵ of optimum and uses no more than z outliers.

Clustering problems are well-studied in a variety of fields such as data science, operations research, and computer science. Such problems include variants of centre location problems, k-median, and k-means to name a few. In some cases, not all data points need to be clustered; some may be discarded for various reasons. For instance, some points may arise from noise in a data set or one might be willing to discard a certain fraction of the points to avoid incurring unnecessary overhead in the cost of a clustering solution. We study clustering problems with outliers. More specifically, we look at UNCAPACITATED FACILITY LOCATION (UFL), k-MEDIAN, and k-MEANS. In these problems, we are given a set χ of data points in a metric space δ(.,.), a set C of possible centres (each maybe with an opening cost), maybe an integer parameter k, plus an additional parameter z as the number of outliers. In UNCAPACITATED FACILITY LOCATION with outliers, we have to open some centres, discard up to z points of χ and assign every other point to the nearest open centre, minimizing the total assignment cost plus centre opening costs. In k-MEDIAN and k-MEANS, we have to open up to k centres but there are no opening costs. In k-MEANS, the cost of assigning j to i is δ2(j, i). We present several results. Our main focus is on cases where δ is a doubling metric (this includes fixed dimensional Euclidean metrics as a special case) or is the shortest path metrics of graphs from a minor-closed family of graphs. For UNIFORM-COST UFL with outliers on such metrics we show that a multiswap simple local search heuristic yields a PTAS. With a bit more work, we extend this to bicriteria approximations for the k-MEDIAN and k-MEANS problems in the same metrics where, for any constant ε > 0, we can find a solution using (1 + ε)k centres whose cost is at most a (1 + ε)-factor of the optimum and uses at most z outliers. Our algorithms are all based on natural multiswap local search heuristics. We also show that natural local search heuristics that do not violate the number of clusters and outliers for k-MEDIAN (or k-MEANS) will have unbounded gap even in Euclidean metrics. Furthermore, we show how our analysis can be extended to general metrics for k-MEANS with outliers to obtain a (25 + ε, 1 + ε)-approximation: an algorithm that uses at most (1 + ε)k clusters and whose cost is at most 25 + ε of optimum and uses no more than z outliers.

We consider scheduling problems in which jobs need to be processed through a (shared) network of machines. The network is given in the form of a graph the edges of which represent the machines. We are also given a set of jobs, each specified by its processing time and a path in the graph. Every job needs to be processed in the order of edges specified by its path. We assume that jobs can wait between machines and preemption is not allowed; that is, once a job is started being processed on a machine, it must be completed without interruption. Every machine can only process one job at a time. The makespan of a schedule is the earliest time by which all the jobs have finished processing. The flow time (a.k.a. the completion time) of a job in a schedule is the difference in time between when it finishes processing on its last machine and when the it begins processing on its first machine. The total flow time (or the sum of completion times) is the sum of flow times (or completion times) of all jobs. Our focus is on finding schedules with the minimum sum of completion times or minimum makespan. In this paper, we develop several algorithms (both approximate and exact) for the problem both on general graphs and when the underlying graph of machines is a tree. Even in the very special case when the underlying network is a simple star, the problem is very interesting as it models a biprocessor scheduling with applications to data migration.

We study a problem that integrates buy-at-bulk network design into the classical facility location problem. We consider a generalization of the facility location problem where multiple clients may share a capacitated network to connect to open facilities instead of requiring direct links. In this problem, we wish to open facilities, build a routing network by installing access cables of different costs and capacities, and route every client demand to an open facility. We provide a path-based formulation and we compare it with the natural compact formulation for this problem. We then design an exact branch-price-and-cut algorithm for solving the path-based formulation. We study the effect of two families of valid inequalities. In addition to this, we present three different types of primal heuristics and employ a hybrid approach to effectively combine these heuristics in order to improve the primal bounds. We finally report the results of our approach that were tested on a set of real world instances, as well as two sets of benchmark instances and evaluate the effects of our valid inequalities and primal heuristics.

The most well-known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly $k$-means: given a set of data points and a parameter $k$, select $k$ centers and partition the data points into $k$ clusters around these centers so that the sum of squares of distances of the points to their cluster center is minimized. Typically these data points lie in Euclidean space $\mathbb{R}^d$ for some $d\geq 2$. $k$-means and the first algorithms for it were introduced in the 1950s. Over the last six decades, hundreds of papers have studied this problem and different algorithms have been proposed for it. The most commonly used algorithm in practice is known as Lloyd--Forgy, which is also referred to as “the” $k$-means algorithm, and various extensions of it often work very well in practice. However, they may produce solutions whose cost is arbitrarily large compared to the optimum solution. Kanungo et al. [ Comput. Geom., 28 (2004), pp. 89--112] analyzed a very simple local search heuristic to get a polynomial-time algorithm with approximation ratio $9+\epsilon$ for any fixed $\epsilon>0$ for $k$-means in Euclidean space. Finding an algorithm with a better worst-case approximation guarantee has remained one of the biggest open questions in this area, in particular, whether one can get a true polynomial-time approximation scheme (PTAS) for fixed dimension Euclidean space. We settle this problem by showing that a simple local search algorithm provides a PTAS for $k$-means for $\mathbb{R}^d$ for any fixed $d$. More precisely, for any error parameter $\epsilon>0$, the local search algorithm that considers swaps of up to $\rho=d^{O(d)}\cdot{\epsilon}^{-O(d/\epsilon)}$ centers at a time will produce a solution using exactly $k$ centers whose cost is at most a $(1+\epsilon)$-factor greater than the optimum solution. Although the algorithm is not practical due to the large polynomial running time, it settles the approximability of this important problem. Our analysis extends very easily to the more general settings where we want to minimize the sum of $q$th powers of the distances between data points and their cluster centers (instead of sum of squares of distances as in $k$-means) for any fixed $q\geq 1$ and where the metric may not be Euclidean but still has fixed doubling dimension. Finally, our techniques also extend to other classic clustering problems. We provide the first demonstration that local search yields a PTAS for uncapacitated facility location and the generalization of $k$-median to the setting with nonuniform opening costs in doubling metrics.