Abstract. We investigate the complexity of solving stable or perturbation-resilient instances of [Formula: see text]-means and [Formula: see text]-median clustering in fixed-dimensional Euclidean metrics (or more generally doubling metrics). The notion of stable or perturbation-resilient instances was introduced by Bilu and Linial [ Are stable instances easy?, 2010] and Awasthi, Blum, and Sheffet [ Stability yields a PTAS for k-median and k-means clustering, IEEE Computer Society, Washington, DC, 2010]. In our context, we say a [Formula: see text]-means instance is [Formula: see text]-stable if there is a unique optimum solution which remains unchanged if distances are (nonuniformly) stretched by a factor of at most [Formula: see text]. Stable clustering instances have been studied to explain why heuristics such as Lloyd’s algorithm perform well in practice. In this work we show that for any fixed [Formula: see text], [Formula: see text]-stable instances of [Formula: see text]-means in doubling metrics, which include fixed-dimensional Euclidean metrics, can be solved in polynomial time. More precisely, we show a natural multiswap local-search algorithm in fact finds the optimum solution for [Formula: see text]-stable instances of [Formula: see text]-means and [Formula: see text]-median in a polynomial number of iterations. We complement this result by showing that it is essentially tight: when the dimension [Formula: see text] is part of the input there is a fixed [Formula: see text] such that there is not even a PTAS for [Formula: see text]-stable [Formula: see text]-means in [Formula: see text] with [Formula: see text] unless NP = RP. To do this, we consider a robust property of CSPs: call an instance stable if there is a unique optimum solution [Formula: see text] and for any other solution [Formula: see text], the number of unsatisfied clauses is proportional to the Hamming distance between [Formula: see text] and [Formula: see text]. Dinur, Goldreich, and Gur have already shown stable QSAT is hard to approximate for some constant [Formula: see text] [ 20 ]. Recently, Paradise [ Comput. Complexity, 30 (2021), 1] extended this to the setting with bounded variable occurrence. More specifically, this implies that stable QSAT with bounded variable occurrence is APX-hard. Given this, we consider “stability-preserving” reductions to prove our hardness for stable [Formula: see text]-means. Such reductions seem to be more fragile and intricate than standard [Formula: see text]-reductions and may be of further use to demonstrate other stable optimization problems are hard to solve.

We consider the well-studied Robust (k,z)-Clustering problem, which generalizes the classic k-Median, k-Means, and k-Center problems and arises in the domains of robust optimization [Anthony, Goyal, Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness [Abbasi, Bhaskara, Venkatasubramanian, 2021 & Ghadiri, Samadi, Vempala, 2022]. Given a constant z ≥ 1, the input to Robust (k,z)-Clustering is a set P of n points in a metric space (M,δ), a weight function w: P → ℝ_{≥ 0} and a positive integer k. Further, each point belongs to one (or more) of the m many different groups S_1,S_2,…,S_m ⊆ P. Our goal is to find a set X of k centers such that max_{i ∈ [m]} ∑_{p ∈ S_i} w(p) δ(p,X)^z is minimized. Complementing recent work on this problem, we give a comprehensive understanding of the parameterized approximability of the problem in geometric spaces where the parameter is the number k of centers. We prove the following results: [(i)] 1) For a universal constant η₀ > 0.0006, we devise a 3^z(1-η₀)-factor FPT approximation algorithm for Robust (k,z)-Clustering in discrete high-dimensional Euclidean spaces where the set of potential centers is finite. This shows that the lower bound of 3^z for general metrics [Goyal, Jaiswal, Inf. Proc. Letters, 2023] no longer holds when the metric has geometric structure. 2) We show that Robust (k,z)-Clustering in discrete Euclidean spaces is (√{3/2}- o(1))-hard to approximate for FPT algorithms, even if we consider the special case k-Center in logarithmic dimensions. This rules out a (1+ε)-approximation algorithm running in time f(k,ε)poly(m,n) (also called efficient parameterized approximation scheme or EPAS), giving a striking contrast with the recent EPAS for the continuous setting where centers can be placed anywhere in the space [Abbasi et al., FOCS'23]. 3) However, we obtain an EPAS for Robust (k,z)-Clustering in discrete Euclidean spaces when the dimension is sublogarithmic (for the discrete problem, earlier work [Abbasi et al., FOCS'23] provides an EPAS only in dimension o(log log n)). Our EPAS works also for metrics of sub-logarithmic doubling dimension.

In the reconciliation $k$-median problem we ask to cluster a set of data points by picking $k$ cluster centers so as to minimize the sum of distances of the data points to their cluster centers plus the sum of pairwise distances between the centers. The problem, which is a variant of classic $k$-median, aims to find a set of cluster centers that are not too far from each other, and it has applications, or example, when selecting a committee to deliberate on a controversial topic. This problem was introduced recently (Ordozgoiti et al., 2019), and it was shown that a local-search-based algorithm is always within a factor $O(k)$ of an optimum solution and performs well in practice. In this paper, we demonstrate a close connection of reconciliation $k$-median to a variant of the $k$-facility location problem, in which each potential cluster center has an individual opening cost and we aim at minimizing the sum of client-center distances and the opening costs. This connection enables us to provide a new algorithm for reconciliation $k$-median that yields a constant-factor approximation (independent of $k$). We also provide a sparsification scheme that reduces the number of potential cluster centers to $O(k)$ in order to substantially speed up approximation algorithms. We empirically compare our new algorithms with the previous local-search approach, showing improved performance and stability. In addition, we show how our sparsification approach helps to reduce computation time without significantly compromising the solution quality.

This paper considers the well-studied algorithmic regime of designing a $(1+\epsilon)$-approximation algorithm for a k-clustering problem that runs in time $f(k,\epsilon)poly(n)$ (sometimes called an efficient parameterized approximation scheme or EPAS for short1). Notable results of this kind include EPASes in the high-dimensional Euclidean setting for k-center [Badŏiu, Har-Peled, Indyk; STOC’02] as well as k-median, and k-means [Kumar, Sabharwal, Sen; J. ACM 2010]. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems (across multiple well-studied objectives as well as metric spaces) and unifies well-known EPASes. More specifically, our algorithm gives EPASes in the following settings:•Clustering objectives: k-means, k-center, k-median, priority k-center, $\ell$-centrum, ordered k-median, socially fair k-median (aka robust k-median), or any other objective that can be formulated as minimizing a monotone (not necessarily symmetric!) norm of the distances of the points from the solution (generalizing the symmetric formulation introduced by Chakrabarty and Swamy [STOC’19]).•Metric spaces: Continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics. Prior to our results, EPASes were only known for vanilla clustering objectives (k-means, k-median, and k-center) and each such algorithm is tailored to work for the specific input metric and clustering objective (e.g., EPASes for k means and k-center in $\mathbb{R}^{d}$ are conceptually very different). In contrast, our algorithmic framework is applicable to a wide range of well-studied objective functions in a uniform way, and is (almost) entirely oblivious to any specific metric structures and yet is able to effectively exploit those unknown structures. In particular, our algorithm is not based on the (metric- and objective-specific) technique of coresets. Key to our analysis is a new concept that we call bounded $\epsilon$-scatter dimension—an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension(often used as a source of algorithmic tractability for geometric problems). Our main technical result shows that two conditions are essentially sufficient for our algorithm to yield an EPAS on the input metric M for any clustering objective:(i)The objective is described by a monotone norm, and(ii)the $\epsilon$-scatter dimension of M is upper bounded by a function of $\epsilon$.1Quick remarks: (i) An EPAS is not comparable to polynomial time approximation schemes (PTAS), (ii) before the term EPAS was invented some researchers call this type of approximation schemes a PTAS or simply an approximation scheme (in clustering, it is often assumed that k is small) [1], [2], and (iii) both EPAS and PTAS are implied by the existence of efficient polynomial time approximation schemes (EPTAS).

In the Demand Strip Packing problem (DSP), we are given a time interval and a collection of tasks, each characterized by a processing time and a demand for a given resource (such as electricity, computational power, etc.). A feasible solution consists of a schedule of the tasks within the mentioned time interval. Our goal is to minimize the peak resource consumption, i.e. the maximum total demand of tasks executed at any point in time. It is known that DSP is NP-hard to approximate below a factor 3/2, and standard techniques for related problems imply a (polynomial-time) 2-approximation. Our main result is a (5/3+eps)-approximation algorithm for any constant eps>0. We also achieve best-possible approximation factors for some relevant special cases.

We investigate the complexity of solving stable or perturbation-resilient instances of k-means and k-median clustering in fixed dimension Euclidean metrics (or more generally doubling metrics). The notion of stable or perturbation resilient instances was introduced by Bilu and Linial [2010] and Awasthi, Blum, and Sheffet [2012]. In our context, we say a k-MEANS instance is α-stable if there is a unique optimum solution which remains unchanged if distances are (non-uniformly) stretched by a factor of at most α. Stable clustering instances have been studied to explain why heuristics such as Lloyd's algorithm perform well in practice. In this work we show that for any fixed ∊ > 0, (1 + ∊)-stable instances of k-MEANS in doubling metrics, which include fixed-dimensional Euclidean metrics, can be solved in polynomial time. More precisely, we show a natural multi-swap local-search algorithm in fact finds the optimum solution for (1 + ∊)-stable instances of k-MEANS and k-median in a polynomial number of iterations. We complement this result by showing that under a plausible PCP hypothesis this is essentially tight: that when the dimension d is part of the input, there is a fixed ∊0 > 0 such there is not even a PTAS for (1 + ∊0)-stable k-MEANS in ℝd unless NP=RP. To do this, we consider a robust property of CSPs; call an instance stable if there is a unique optimum solution x* and for any other solution x’, the number of unsatisfied clauses is proportional to the Hamming distance between x* and x’. Dinur, Goldreich, and Gur have already shown stable QSAT is hard to approximation for some constant Q [16], our hypothesis is simply that stable QSAT with bounded variable occurrence is also hard (there is in fact work in progress to prove this hypothesis). Given this hypothesis, we consider “stability-preserving” reductions to prove our hardness for stable k-MEANS. Such reductions seem to be more fragile and intricate than standard L-reductions and may be of further use to demonstrate other stable optimization problems are hard to solve.

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 consider the problem of fair allocation of indivisible goods where we are given a set I of m indivisible resources (items) and a set P of n customers (players) competing for the resources. Each resource j in I has a same value vj > 0 for a subset of customers interested in j and it has no value for other customers. The goal is to find a feasible allocation of the resources to the interested customers such that in the Max-Min scenario (also known as Santa Claus problem) the minimum utility (sum of the resources) received by each of the customers is as high as possible and in the Min-Max case (also known as R||C_max problem), the maximum utility is as low as possible. In this paper we are interested in instances of the problem that admit a PTAS. These instances are not only of theoretical interest but also have practical applications. For the Max-Min allocation problem, we start with instances of the problem that can be viewed as a convex bipartite graph; there exists an ordering of the resources such that each customer is interested (has positive evaluation) in a set of consecutive resources and we demonstrate a PTAS. For the Min-Max allocation problem, we obtain a PTAS for instances in which there is an ordering of the customers (machines) and each resource (job) is adjacent to a consecutive set of customers (machines). Next we show that our method for the Max-Min scenario, can be extended to a broader class of bipartite graphs where the resources can be viewed as a tree and each customer is interested in a sub-tree of a bounded number of leaves of this tree (e.g. a sub-path).

We consider sequential balls-into-bins processes that randomly allocate m balls into n bins. We analyze two allocation schemes that achieve a close to optimal maximum load of ⌈m/n⌉ + 1 and require only O(m) (expected) allocation time. These parameters should be compared with the classic d-choice-process which achieves a maximum load of m/n + log log n/d + O(1) and requires m • d allocation time.