Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
From MaRDI portal
Publication:5388006
DOI10.1287/moor.1060.0218zbMath1278.90146OpenAlexW2097078863WikidataQ56004686 ScholiaQ56004686MaRDI QIDQ5388006
Rafail Ostrovsky, Julia Chuzhoy, Yuval Rabani
Publication date: 27 May 2008
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/6187aed77b89809a9a04c8786209da90a9dce89c
Related Items
Inverse interval scheduling via reduction on a single machine ⋮ On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ On Lagrangian relaxation for constrained maximization and reoptimization problems ⋮ Non-preemptive speed scaling ⋮ Interval scheduling and colorful independent sets ⋮ Min Sum Edge Coloring in Multigraphs Via Configuration LP ⋮ The complexity of the timetable‐based railway network design problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization ⋮ Bandwidth allocation in cellular networks with multiple interferences ⋮ Maximizing Throughput in Flow Shop Real-Time Scheduling ⋮ Improving LTL truck load utilization on line ⋮ Grasp and delivery for moving objects on broken lines ⋮ Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment ⋮ On Lagrangian Relaxation and Subset Selection Problems ⋮ Balanced splitting on weighted intervals ⋮ The temporal explorer who returns to the base ⋮ Throughput scheduling with equal additive laxity ⋮ Throughput scheduling with equal additive laxity ⋮ Scheduling with a minimum number of machines ⋮ Bandwidth-constrained allocation in grid computing ⋮ Priority algorithms for the subset-sum problem ⋮ Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores ⋮ A polynomial-time approximation scheme for the airplane refueling problem ⋮ Efficient job scheduling algorithms with multi-type contentions