We consider the Vector Scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given n jobs, represented as d-dimensional vectors in $$[0,1]^d$$ , and m identical machines, and the goal is to assign the jobs to machines such that the maximum load of each machine over all the coordinates is at most 1. For fixed d, the problem admits an approximation scheme, and the best known running time is $$n^{f(\epsilon ,d)}$$ where $$f(\epsilon ,d) = (1/\epsilon )^{\tilde{O}(d)}$$ ( $$\tilde{O}$$ suppresses polylogarithmic terms in d). In particular, the dependence on d is double exponential. In this paper we show that a double exponential dependence on d is necessary, and give an improved algorithm with essentially optimal running time. Specifically, we let $$\exp (x)$$ denote $$2^x$$ and show that: (1) For any $$\epsilon <1$$ , there is no $$(1+\epsilon )$$ -approximation with running time $$\exp \left( o(\lfloor 1/\epsilon \rfloor ^{d/3})\right) $$ unless the Exponential Time Hypothesis fails. (2) No $$(1+\epsilon )$$ -approximation with running time $$\exp \left( \lfloor 1/\epsilon \rfloor ^{o(d)}\right) $$ exists, unless NP has subexponential time algorithms. (3) Similar lower bounds also hold even if $$\epsilon m$$ extra machines are allowed (i.e. with resource augmentation), for sufficiently small $$\epsilon >0$$ . (4) We complement these lower bounds with a $$(1+\epsilon )$$ -approximation that runs in time $$\exp \left( (1/\epsilon )^{O(d \log \log d)}\right) + nd$$ . This gives the first efficient approximation scheme (EPTAS) for the problem.

We study the Minimum Latency Submodular Cover (MLSC) problem, which consists of a metric ( V , d ) with source r ∈ V and m monotone submodular functions f 1 , f 2 , …, f m : 2 V → [0, 1]. The goal is to find a path originating at r that minimizes the total “cover time” of all functions. This generalizes well-studied problems, such as Submodular Ranking [Azar and Gamzu 2011] and the Group Steiner Tree [Garg et al. 2000]. We give a polynomial time O (log 1/ϵ ċ log 2+δ |V|)-approximation algorithm for MLSC, where ϵ > 0 is the smallest non-zero marginal increase of any { f i } m i = 1 and δ > 0 is any constant. We also consider the Latency Covering Steiner Tree (LCST) problem, which is the special case of MLSC where the f i s are multi-coverage functions. This is a common generalization of the Latency Group Steiner Tree [Gupta et al. 2010; Chakrabarty and Swamy 2011] and Generalized Min-sum Set Cover [Azar et al. 2009; Bansal et al. 2010] problems. We obtain an O (log 2 | V |)-approximation algorithm for LCST. Finally, we study a natural stochastic extension of the Submodular Ranking problem and obtain an adaptive algorithm with an O (log 1/ϵ)-approximation ratio, which is best possible. This result also generalizes some previously studied stochastic optimization problems, such as Stochastic Set Cover [Goemans and Vondrák 2006] and Shared Filter Evaluation [Munagala et al. 2007; Liu et al. 2008].

In this article, we consider k‐way vertex cut: the problem of finding a graph separator of a given size that decomposes the graph into the maximum number of components. Our main contribution is the derivation of an efficient polynomial‐time approximation scheme for the problem on planar graphs. Also, we show that k‐way vertex cut is polynomially solvable on graphs of bounded treewidth and fixed–parameter tractable on planar graphs with the size of the separator as the parameter. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 170–178 2014

In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets S = {S_1, S_2, ..., S_m} where each set S_i in 2^{[n]} has a positive requirement k(S_i) that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set S_i is defined as the first index j in the ordering such that the first j elements in the ordering contain k(S_i) elements in S_i. This problem was introduced by [Azar, Gamzu and Yin, 2009] with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known [Bansal, Gupta and Krishnaswamy, 2010][Skutella and Williamson, 2011]. We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set S is covered in the moment when k(S) amount of elements in S are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming and analysis are completely different from [Bansal, Gupta and Krishnaswamy, 2010][Skutella and Williamson, 2011]. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved 12.4-approximation for the non-preemptive problem.