Dynamic algorithms for monotonic interval scheduling problem

DOI10.1016/J.TCS.2014.09.046zbMATH Open1303.68167arXiv1412.8005OpenAlexW1417332038MaRDI QIDQ476865FDOQ476865

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

Publication date: 2 December 2014

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

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.

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

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

zbMATH Keywords

data structuresdynamic algorithmsinterval scheduling

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Dynamising Interval Scheduling: The Monotonic Case
• Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals
• New partitioning techniques and faster algorithms for approximate interval scheduling
• Title not available (Why is that?)
• Dynamic interval scheduling for multiple machines
• Title not available (Why is that?)
• The hull number in the convexity of induced paths of order \(3\)
• On streaming algorithms for geometric independent set and clique

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)