Approximation algorithms for job scheduling with block-type conflict graphs
From MaRDI portal
Publication:6568400
DOI10.1016/J.COR.2024.106606MaRDI QIDQ6568400
Krzysztof Turowski, Inka Sokołowska, Tytus Pikies, Hanna Furmańczyk
Publication date: 8 July 2024
Published in: Computers \& Operations Research (Search for Journal in Brave)
schedulingblock graphconflict graphincompatibility graphuniform machineidentical machineunrelated machine
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for scheduling unrelated parallel machines
- Scheduling with incompatible jobs
- Mutual exclusion scheduling
- Approximation schemes for scheduling on uniformly related and identical parallel machines
- Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms
- Makespan minimization on unrelated parallel machines with a few bags
- Scheduling identical jobs on uniform machines with a conflict graph
- An exact algorithm for parallel machine scheduling with conflicts
- A unified framework for designing EPTAS for load balancing on parallel machines
- An optimal rounding gives a better approximation for scheduling unrelated machines
- Maximum Flows by Incremental Breadth-First Search
- Scheduling identical jobs on uniform parallel machines
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- A Characterization of Block-Graphs
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- On minimizing the makespan when some jobs cannot be assigned on the same machine
- Max flows in O(nm) time, or better
- Parameterized Algorithms
- Bounds for Certain Multiprocessing Anomalies
- An EPTAS for scheduling on unrelated machines of few different types
This page was built for publication: Approximation algorithms for job scheduling with block-type conflict graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6568400)
