Dynamic algorithms for monotonic interval scheduling problem

DOI10.1016/J.TCS.2014.09.046MaRDI QIDQ476865zbMATH OpenOpenAlexFDO

Authors Bakhadyr Khoussainov, Mikhail Kokho, Jiamou Liu, Alexander Gavryushkin

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

data structuresdynamic algorithmsinterval scheduling

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Data structures (68P05)

Abstract: We investigate dynamic algorithms for the interval scheduling problem. Our algorithm runs in amortised time $O(logn)$ for query operation and $O(dlo{g}^{2}n)$ for insertion and removal operations, where $n$ and $d$ are the maximal numbers of intervals and pairwise overlapping intervals respectively. We also show that for a monotonic set, that is when no interval properly contains another interval, the amortised complexity is $O(logn)$ for both query and update operations. We compare the two algorithms for the monotonic interval sets using experiments.

Recommendations

• Dynamising Interval Scheduling: The Monotonic Case
• Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals
• Dynamic interval scheduling for multiple machines
• scientific article; zbMATH DE number 1003261
• Data structures for incremental interval coloring

Cites work

• scientific article; zbMATH DE number 1003261 (Why is no real title available?)
• A data structure for dynamic trees
• A new representation of proper interval graphs with an application to clique-width
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Dynamic rectangular intersection with priorities
• Dynamising Interval Scheduling: The Monotonic Case
• Interval scheduling: A survey
• Introduction to algorithms
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Maintenance of a piercing set for intervals with applications
• Online Interval Scheduling: Randomized and Multiprocessor Cases
• Self-adjusting binary search trees

Cited in

(8)

• Dynamic interval scheduling for multiple machines
• New partitioning techniques and faster algorithms for approximate interval scheduling
• The hull number in the convexity of induced paths of order \(3\)
• Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals
• Dynamising Interval Scheduling: The Monotonic Case
• scientific article; zbMATH DE number 1946760 (Why is no real title available?)
• On streaming algorithms for geometric independent set and clique
• scientific article; zbMATH DE number 7651158 (Why is no real title available?)

This page was built for publication: Dynamic algorithms for monotonic interval scheduling problem

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