New partitioning techniques and faster algorithms for approximate interval scheduling

DOI10.1007/S00453-024-01252-1MaRDI QIDQ6614114

Slobodan Mitrović, Spencer Compton, Ronitt Rubinfeld

Publication date: 7 October 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

dynamic algorithmsjob schedulinginterval schedulinglocal computation algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dynamic algorithms for monotonic interval scheduling problem
• Scheduling jobs with fixed start and end times
• Label placement by maximum independent set in rectangles
• Dynamic Interval Scheduling for Multiple Machines
• Interval scheduling: A survey
• Approximation schemes for covering and packing problems in image processing and VLSI
• Complexity of Scheduling under Precedence Constraints
• A Set Partitioning Approach to the Crew Scheduling Problem
• A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
• Stochastic Machine Scheduling with Precedence Constraints
• Single-Machine Scheduling with Precedence Constraints
• Scheduling
• Worst-Case Efficient Dynamic Geometric Independent Set

This page was built for publication: New partitioning techniques and faster algorithms for approximate interval scheduling

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