Search

We investigate offline and online algorithms for Round - UFPP , the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. Round - UFPP is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for Round - UFPP without the NBA. We first study offline Round - UFPP for a restricted class of instances, called α -small, where the size of each flow is at most α times the capacity of its bottleneck edge, and present an O (log (1 / (1 - α))) -approximation algorithm. Next, our main result is an online O (log log c max) -competitive algorithm for Round - UFPP where c max is the largest edge capacity, improving upon the previous best bound of O (log c max) due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline O (min (log n , log m , log log c max)) -approximation algorithm and an online O (min (log m , log log c max)) -competitive algorithm for Round - UFPP , where n is the number of flows and m is the number of edges. [ABSTRACT FROM AUTHOR]

We study the restricted case of Scheduling on Unrelated Parallel Machines. In this problem, we are given a set of jobs J with processing times pj and each job may be scheduled only on some subset of machines Sj⊆ M. The goal is to find an assignment of jobs to machines to minimize the time within which all jobs can be processed. In a seminal paper, Lenstra, Shmoys, and Tardos [Proceedings of the 28th Annual IEEE Conference on Foundations of Computer Science, 1987, pp. 217--224] designed an elegant 2-approximation for the problem. The question of whether approximation algorithms with better guarantees exist for this classic scheduling problem has since remained a source of mystery. In recent years, with the improvement of our understanding of configuration linear programs, it now appears an attainable goal to design such an algorithm. Our main contribution in this paper is to make progress towards this goal. For the so-called (1, ε)-case, when the processing times of jobs are either 1 or ε ∊ (0, 1), we design an approximation algorithm whose guarantee tends to 1+√3/2 ≈ 1.866025 as ε tends to zero. This improves on the 2 ε0 guarantee recently obtained by Chakrabarty, Khanna, and Li [Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2015, pp. 1087--1101] for some constant ε0 > 0. Further, the ideas presented in this paper do not crucially depend on the fact that the instances contain exactly two different job sizes; i.e., they extend also to families of instances more general than the (1, ε)-case. In a certain precise sense, we fall slightly short of improving on the 30-year-old classic algorithm of Lenstra, Shmoys, and Tardos [Proceedings of the 28th Annual IEEE Conference on Foundations of Computer Science, 1987, pp. 217--224] for the restricted case. [ABSTRACT FROM AUTHOR]

We consider the problem of designing truthful mechanisms for scheduling n tasks on a set of m parallel related machines in order to minimize the makespan. In what follows, we consider that each task is owned by a selfish agent. This is a variant of the KP-model introduced by Koutsoupias and Papadimitriou (Proc. of STACS 1999, pp. 404–413, ) (and of the CKN-model of Christodoulou et al. in Proc. of ICALP 2004, pp. 345–357, ) in which the agents cannot choose the machine on which their tasks will be executed. This is done by a centralized authority, the scheduler. However, the agents may manipulate the scheduler by providing false information regarding the length of their tasks. We introduce the notion of increasing algorithm and a simple reduction that transforms any increasing algorithm into a truthful one. Furthermore, we show that some of the classical scheduling algorithms are indeed increasing: the LPT algorithm, the PTAS of Graham (SIAM J. Appl. Math. 17(2):416–429, ) in the case of two machines, as well as a simple PTAS for the case of m machines, with m a fixed constant. Our results yield a randomized r(1+ ε)-approximation algorithm where r is the ratio between the largest and the smallest speed of the related machines. Furthermore, by combining our approach with the classical result of Shmoys et al. (SIAM J. Comput. 24(6):1313–1331, ), we obtain a randomized 2 r(1+ ε)-competitive algorithm. It has to be noticed that these results are obtained without payments, unlike most of the existing works in the field of Mechanism Design. Finally, we show that if payments are allowed then our approach gives a (1+ ε)-algorithm for the off-line case with related machines. [ABSTRACT FROM AUTHOR]