We present an efficient polynomial-time approximation scheme (EPTAS) for the problem of scheduling jobs on parallel uniform machines that improves all previously known EPTAS for the problem. Our algorithm uses a Mixed Integer Linear Program (MILP) formulation for a relaxed version of the problem. We simplify the MILP by repeatedly removing carefully selected sets of jobs and machines until all integer variables have been removed. Then, we build up the solution through the use of a dynamic programming approach, enumeration, and linear program solving. Notable about our approach is that our algorithm only uses an LP solver, different from previous EPTAS approaches where MILP solvers are necessary.

Unmanned aerial vehicles, or drones, have gained a lot of popularity due to their large number of applications in surveillance, aerial photography, 3D mapping, search and rescue operations, and shipping and delivery of goods. A critical task in the deployment of drones is the computation of effective flying paths that allow drones to reach their destinations while avoiding obstacles and minimizing the amount of energy that they need to consume. We present a novel path planning algorithm that is not only faster and uses less memory than other existing path planning algorithms, but it also produces shorter paths. All these performance metric improvements lead to a more energy efficient path planning algorithm for autonomous drones.

BACKGROUND: De novo genome assembly of next-generation sequencing data is one of the most important current problems in bioinformatics, essential in many biological applications. In spite of significant amount of work in this area, better solutions are still very much needed. RESULTS: We present a new program, SAGE, for de novo genome assembly. As opposed to most assemblers, which are de Bruijn graph based, SAGE uses the string-overlap graph. SAGE builds upon great existing work on string-overlap graph and maximum likelihood assembly, bringing an important number of new ideas, such as the efficient computation of the transitive reduction of the string overlap graph, the use of (generalized) edge multiplicity statistics for more accurate estimation of read copy counts, and the improved use of mate pairs and min-cost flow for supporting edge merging. The assemblies produced by SAGE for several short and medium-size genomes compared favourably with those of existing leading assemblers. CONCLUSIONS: SAGE benefits from innovations in almost every aspect of the assembly process: error correction of input reads, string-overlap graph construction, read copy counts estimation, overlap graph analysis and reduction, contig extraction, and scaffolding. We hope that these new ideas will help advance the current state-of-the-art in an essential area of research in genomics.

We study the following square packing problem: Given a set Q of squares with positive profits, the goal is to pack a subset of Q into a rectangular bin $\mathcal R$ so that the total profit of the squares packed in $\mathcal R$ is maximized. Squares must be packed so that their sides are parallel to those of $\mathcal R$. We present a polynomial time approximation scheme for the problem, which for any value $\epsilon > 0$ finds and packs a subset $Q' \subseteq Q$ of profit at least $(1-\epsilon) OPT$, where $OPT$ is the profit of an optimum solution.

In this paper we present a linear time approximation scheme for the job shop scheduling problem with a fixed number of machines and fixed number of operations per job. This improves on the previously best $2+\epsilon$, $\epsilon > 0$, approximation algorithm for the problem by Shmoys, Stein, and Wein [SIAM J. Comput., 23 (1994), pp. 617--632]. Our approximation scheme is very general and it can be extended to the case of job shop scheduling problems with release and delivery times, multistage job shops, dag job shops, and preemptive variants of most of these problems.