Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters can protect up to B vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not been protected so far. The task is to find the smallest B that allows for saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2 even on trees unless P = NP (King and MacGillivray in Discret Math 310(3):614–621, 2010). Chalermsook and Chuzhoy (In: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, Texas, USA, 17–19 Jan 2010, SIAM, pp 1334–1349, 2010) presented a Linear Programming (LP) based $$O(\log ^* n)$$ approximation for RMFC on trees that matches the integrality gap of the natural Linear Programming relaxation. This was recently improved by Adjiashvili et al. (ACM Trans Algorithms 15(2):20:1–20:33, 2019) to a 12-approximation through a combination of LP rounding along with several new techniques. In this paper we present an asymptotic QPTAS for RMFC on trees. More specifically, let $$\epsilon >0$$ , and $$\mathcal {I}$$ be an instance of RMFC where the optimum number of firefighters to save all the leaves is $$OPT(\mathcal {I})$$ . We present an algorithm which uses at most $$\lceil (1+\epsilon )OPT(\mathcal {I})\rceil $$ many firefighters at each time step and runs in time $$n^{O(\log \log n/\epsilon )}$$ . This suggests that the existence of an asymptotic PTAS is plausible especially since the exponent is $$O(\log \log n)$$ , not $$O(\log n)$$ . Our result combines a more refined height reduction lemma than the one in Adjiashvili et al. (2019) with LP rounding and dynamic programming to find the solution. We also apply our height reduction lemma to the algorithm provided in Adjiashvili et al. (2019) plus a more careful analysis to improve their 12-approximation and provide a polynomial time ( $$5+\epsilon $$ )-approximation.

In this paper we study the classical problem of throughput maximization. In this problem we have a collection J of n jobs, each having a release time r_j, deadline d_j, and processing time p_j. They have to be scheduled non-preemptively on m identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their [r_j,d_j] window. This problem has been studied extensively (even for the case of m = 1). Several special cases of the problem remain open. Bar-Noy et al. [STOC1999] presented an algorithm with ratio 1-1/(1+1/m)^m for m machines, which approaches 1-1/e as m increases. For m = 1, Chuzhoy-Ostrovsky-Rabani [FOCS2001] presented an algorithm with approximation with ratio 1-1/e-ε (for any ε > 0). Recently Im-Li-Moseley [IPCO2017] presented an algorithm with ratio 1-1/e+ε₀ for some absolute constant ε₀ > 0 for any fixed m. They also presented an algorithm with ratio 1-O(√(log m/m))-ε for general m which approaches 1 as m grows. The approximability of the problem for m = O(1) remains a major open question. Even for the case of m = 1 and c = O(1) distinct processing times the problem is open (Sgall [ESA2012]). In this paper we study the case of m = O(1) and show that if there are c distinct processing times, i.e. p_j’s come from a set of size c, then there is a randomized (1-ε)-approximation that runs in time O(n^{mc⁷ε^(-6)}log T), where T is the largest deadline. Therefore, for constant m and constant c this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning.

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.