Interval scheduling maximizing minimum coverage

DOI10.1016/J.DAM.2016.08.021MaRDI QIDQ528573zbMATH OpenOpenAlexFDO

Authors Veli Mäkinen, Valeria Staneva, Alexandru I. Tomescu, Daniel Valenzuela, Sebastian Wilzbach

Publication date 12 May 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.07820, http://hdl.handle.net/10138/307575

zbMATH Keywords

interval schedulinghaplotype assemblymax-flowsread pruning

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Abstract: In the classical interval scheduling type of problems, a set of $n$ jobs, characterized by their start and end time, need to be executed by a set of machines, under various constraints. In this paper we study a new variant in which the jobs need to be assigned to at most $k$ identical machines, such that the minimum number of machines that are busy at the same time is maximized. This is relevant in the context of genome sequencing and haplotyping, specifically when a set of DNA reads aligned to a genome needs to be pruned so that no more than $k$ reads overlap, while maintaining as much read coverage as possible across the entire genome. We show that the problem can be solved in time $minleft(O(n^{2}logk/logn),O(nklogk)ight)$ by using max-flows. We also give an $O(nlogn)$-time approximation algorithm with approximation ratio $ho=fracklfloork/2floor$.

Recommendations

• Minimum interval cover and its application to genome sequencing
• Scheduling Split Intervals
• The k-track assignment problem
• Interval scheduling on related machines
• Interval scheduling: A survey

Cites work

• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• An Optimal Solution for the Channel-Assignment Problem
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Interval scheduling on identical machines
• Interval scheduling: A survey
• Introduction to algorithms.
• Max flows in \(O(nm)\) time, or better
• Maximal Flow Through a Network
• Scheduling jobs with fixed start and end times
• The k-track assignment problem

Cited in

(4)

• Minimum interval cover and its application to genome sequencing
• Scheduling Split Intervals
• Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times
• Visiting infinitely often the unit interval while minimizing the idle time of high priority segments

Describes a project that uses

Uses Software

• WhatsHap

This page was built for publication: Interval scheduling maximizing minimum coverage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528573)