We consider a new scheduling problem on parallel identical machines in which the number of machines is initially not known, but it follows a given probability distribution. Only after all jobs are assigned to a given number of bags, the actual number of machines is revealed. Subsequently, the jobs need to be assigned to the machines without splitting the bags. This is the stochastic version of a related problem introduced by Stein and Zhong [SODA 2018, TALG 2020] and it is, for example, motivated by bundling jobs that need to be scheduled by data centers. We present two PTASs for the stochastic setting, computing job-to-bag assignments that (i) minimize the expected maximum machine load and (ii) maximize the expected minimum machine load (like in the Santa Claus problem), respectively. The former result follows by careful enumeration combined with known PTASs. For the latter result, we introduce an intricate dynamic program that we apply to a suitably rounded instance.

Clustering is a fundamental problem setting with applications in many different areas. For a given set of points in a metric space and an integer k, we seek to partition the given points into k clusters. For each computed cluster, one typically defines one point as the center of the cluster. A natural objective is to minimize the sum of the cluster center's radii, where we assign the smallest radius r to each center such that each point in the cluster is at a distance of at most r from the center. The best-known polynomial time approximation ratio for this problem is 3.389. In the setting with outliers, i.e., we are given an integer m and allow up to m points that are not in any cluster, the best-known approximation factor is 12.365.

The Cable-Trench Problem (CTP) is a common generalization of the Single-Source Shortest Paths Problem (SSSP) and the Minimum Spanning Tree Problem (MST): given an edge-weighted graph with a special root vertex and parameters τ , γ ≥ 0 , the goal is to find a spanning tree that minimizes the total edge costs plus the total cost of the paths from each vertex to the root, scaled by τ and γ , respectively. While it is well known that both SSSP and MST can be solved in polynomial time, CTP is NP -hard. We show that computing an approximate solution with factor less than 1.000475 is NP -hard, thus ruling out a polynomial-time approximation scheme, unless P = NP . We also consider the more general Steiner Cable-Trench Problem (SCTP), for which only a given subset of terminal vertices must be spanned by a solution. The tree might include non-terminal vertices, known as Steiner vertices, although only paths from terminals to the root are considered in the total cost. For this problem, we present a ( 2 . 88 + ϵ ) -approximation based on a counting argument, for any ϵ > 0 ; also, we give a simple parameterized algorithm with the number of terminals as parameter.

The Cable-Trench Problem (CTP) is an optimization problem that generalizes both the Single-Destination Shortest Path Problem and the Minimum Spanning Tree Problem. Given an edge weighted graph with a special root vertex and parameters τ, γ ≥ 0, the objective is to find a rooted spanning tree that minimizes the weight of the tree, scaled by τ, plus the sum of the weights over all shortest paths from the root, scaled by γ. While each of the generalized problems are well-known to be polynomial-time solvable, CTP is NP-hard. In this paper, we show that even finding an approximation with factor of 1.000475 is NP-hard, thus ruling out the existence of a polynomial-time approximation scheme, unless P = NP.