Source author record

Eric Angel

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graph with Bounded Tree-width

In this paper we study a scheduling problem arising from executing numerical simulations on HPC architectures. With a constant number of parallel machines, the objective is to minimize the makespan under memory constraints for the machines. Those constraints come from a neighborhood graph G for the jobs. Motivated by a previous result on graphs G with bounded path-width, our focus is on the case when the neighborhood graph G has bounded tree-width. Our result is a bi-criteria fully polynomial time approximation algorithm based on a dynamic programming algorithm. It allows to find a solution within a factor of 1 + epsilon of the optimal makespan, where the memory capacity of the machines may be exceeded by a factor at most 1 + epsilon. This result relies on the use of a nice tree decomposition of G and its traversal in a specific way which may be useful on its own. The case of unrelated machines is also tractable with minor modifications.

preprint2020arXiv

Calibrations Scheduling Problem with Arbitrary Lengths and Activation Length

Bender et al. (SPAA 2013) have proposed a theoretical framework for testing in contexts where safety mistakes must be avoided. Testing in such a context is made by machines that need to be often calibrated. Given that calibration costs, it is important to study policies minimizing the calibration cost while performing all the necessary tests. We focus on the single-machine setting and we extend the model proposed by Bender et al. by considering that the jobs have arbitrary processing times and that the preemption of jobs is allowed. For this case, we propose an optimal polynomial time algorithm. Then, we study the case where there are several types of calibrations with different lengths and costs. We first prove that the problem becomes NP-hard for arbitrary processing times even when the preemption of the jobs is allowed. Finally, we focus on the case of unit-time jobs and we show that a more general problem, where the recalibration of the machine is not instantaneous but takes time, can be solved in polynomial time.

preprint2016arXiv

Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach

In this paper, we study the $k$ -forest problem in the model of resource augmentation. In the $k$ -forest problem, given an edge-weighted graph $G(V,E)$ , a parameter $k$ , and a set of $m$ demand pairs $\subseteq V \times V$ , the objective is to construct a minimum-cost subgraph that connects at least $k$ demands. The problem is hard to approximate---the best-known approximation ratio is $O(\min\{\sqrt{n}, \sqrt{k}\})$ . Furthermore, $k$ -forest is as hard to approximate as the notoriously-hard densest $k$ -subgraph problem. While the $k$ -forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor. First, we restate the problem in terms of the number of demands that are {\em not} connected. In particular, the objective of the $k$ -forest problem can be viewed as to remove at most $m-k$ demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way. Specifically, we present a polynomial-time algorithm for the $k$ -forest problem that, for every $ε>0$ , removes at most $m-k$ demands and has cost no more than $O(1/ε^{2})$ times the cost of an optimal algorithm that removes at most $(1-ε)(m-k)$ demands.

preprint2014arXiv

Throughput Maximization in Multiprocessor Speed-Scaling

We are given a set of $n$ jobs that have to be executed on a set of $m$ speed-scalable machines that can vary their speeds dynamically using the energy model introduced in [Yao et al., FOCS'95]. Every job $j$ is characterized by its release date $r_j$ , its deadline $d_j$ , its processing volume $p_{i,j}$ if $j$ is executed on machine $i$ and its weight $w_j$ . We are also given a budget of energy $E$ and our objective is to maximize the weighted throughput, i.e. the total weight of jobs that are completed between their respective release dates and deadlines. We propose a polynomial-time approximation algorithm where the preemption of the jobs is allowed but not their migration. Our algorithm uses a primal-dual approach on a linearized version of a convex program with linear constraints. Furthermore, we present two optimal algorithms for the non-preemptive case where the number of machines is bounded by a fixed constant. More specifically, we consider: {\em (a)} the case of identical processing volumes, i.e. $p_{i,j}=p$ for every $i$ and $j$ , for which we present a polynomial-time algorithm for the unweighted version, which becomes a pseudopolynomial-time algorithm for the weighted throughput version, and {\em (b)} the case of agreeable instances, i.e. for which $r_i \le r_j$ if and only if $d_i \le d_j$ , for which we present a pseudopolynomial-time algorithm. Both algorithms are based on a discretization of the problem and the use of dynamic programming.

preprint2013arXiv

Throughput Maximization in the Speed-Scaling Setting

We are given a set of $n$ jobs and a single processor that can vary its speed dynamically. Each job $J_j$ is characterized by its processing requirement (work) $p_j$ , its release date $r_j$ and its deadline $d_j$ . We are also given a budget of energy $E$ and we study the scheduling problem of maximizing the throughput (i.e. the number of jobs which are completed on time). We propose a dynamic programming algorithm that solves the preemptive case of the problem, i.e. when the execution of the jobs may be interrupted and resumed later, in pseudo-polynomial time. Our algorithm can be adapted for solving the weighted version of the problem where every job is associated with a weight $w_j$ and the objective is the maximization of the sum of the weights of the jobs that are completed on time. Moreover, we provide a strongly polynomial time algorithm to solve the non-preemptive unweighed case when the jobs have the same processing requirements. For the weighted case, our algorithm can be adapted for solving the non-preemptive version of the problem in pseudo-polynomial time.

preprint2011arXiv

Speed Scaling on Parallel Processors with Migration

We study the problem of scheduling a set of jobs with release dates, deadlines and processing requirements (or works), on parallel speed-scaled processors so as to minimize the total energy consumption. We consider that both preemption and migration of jobs are allowed. An exact polynomial-time algorithm has been proposed for this problem, which is based on the Ellipsoid algorithm. Here, we formulate the problem as a convex program and we propose a simpler polynomial-time combinatorial algorithm which is based on a reduction to the maximum flow problem. Our algorithm runs in $O(nf(n)logP)$ time, where $n$ is the number of jobs, $P$ is the range of all possible values of processors' speeds divided by the desired accuracy and $f(n)$ is the complexity of computing a maximum flow in a layered graph with O(n) vertices. Independently, Albers et al. \cite{AAG11} proposed an $O(n^2f(n))$ -time algorithm exploiting the same relation with the maximum flow problem. We extend our algorithm to the multiprocessor speed scaling problem with migration where the objective is the minimization of the makespan under a budget of energy.

preprint2010arXiv

Optimal Data Placement on Networks With Constant Number of Clients

We introduce optimal algorithms for the problems of data placement (DP) and page placement (PP) in networks with a constant number of clients each of which has limited storage availability and issues requests for data objects. The objective for both problems is to efficiently utilize each client's storage (deciding where to place replicas of objects) so that the total incurred access and installation cost over all clients is minimized. In the PP problem an extra constraint on the maximum number of clients served by a single client must be satisfied. Our algorithms solve both problems optimally when all objects have uniform lengths. When objects lengths are non-uniform we also find the optimal solution, albeit a small, asymptotically tight violation of each client's storage size by $ε$ lmax where lmax is the maximum length of the objects and $ε$ some arbitrarily small positive constant. We make no assumption on the underlying topology of the network (metric, ultrametric etc.), thus obtaining the first non-trivial results for non-metric data placement problems.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.