Interval scheduling maximizing minimum coverage

DOI10.1016/J.DAM.2016.08.021zbMATH Open1370.68040arXiv1508.07820OpenAlexW2962935915MaRDI QIDQ528573FDOQ528573

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)

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$.

Full work available at URL: https://arxiv.org/abs/1508.07820

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

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)

Cites Work

• Maximal Flow Through a Network
• Introduction to algorithms.
• Scheduling jobs with fixed start and end times
• Max flows in \(O(nm)\) time, or better
• Interval scheduling: A survey
• Title not available (Why is that?)
• The \(k\)-track assignment problem
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Interval scheduling on identical machines
• An Optimal Solution for the Channel-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

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)