scientific article; zbMATH DE number 7650084

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.17MaRDI QIDQ5875469

Orestis Papadigenopoulos, Dimitris Fotakis, Jannik Matuschke

Publication date: 3 February 2023

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

schedulingapproximationparallelmachinesuniformspeedsunrelatedjobsmalleablemoldable

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds

Cites Work

• Approximation algorithms for scheduling unrelated parallel machines
• Strong LP formulations for scheduling splittable jobs on unrelated machines
• UET scheduling with unit interprocessor communication delays
• Linear-Time approximation schemes for scheduling malleable parallel tasks
• An approximation algorithm for scheduling malleable tasks under general precedence constraints
• Towards an Architecture-Independent Analysis of Parallel Algorithms
• Complexity of Scheduling Parallel Task Systems
• Bounds for Multiprocessor Scheduling with Resource Constraints
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• The Parallel Evaluation of General Arithmetic Expressions
• Precedence-Constrained Scheduling of Malleable Jobs with Preemption
• A $\frac32$‐Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks
• Approximation Algorithms for Scheduling Parallel Jobs
• Bounds on Multiprocessing Timing Anomalies
• An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays

This page was built for publication: