A constant-factor approximation for generalized malleable scheduling under M^ -concave processing speeds

DOI10.1007/978-3-031-06901-7_18MaRDI QIDQ2164700zbMATH OpenOpenAlexFDO

Authors Dimitris Fotakis, Jannik Matuschke, Orestis Papadigenopoulos

Publication date 16 August 2022

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

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Abstract: In generalized malleable scheduling, jobs can be allocated and processed simultaneously on multiple machines so as to reduce the overall makespan of the schedule. The required processing time for each job is determined by the joint processing speed of the allocated machines. We study the case that processing speeds are job-dependent $M^{a}tural$-concave functions and provide a constant-factor approximation for this setting, significantly expanding the realm of functions for which such an approximation is possible. Further, we explore the connection between malleable scheduling and the problem of fairly allocating items to a set of agents with distinct utility functions, devising a black-box reduction that allows to obtain resource-augmented approximation algorithms for the latter.

Recommendations

• Algorithms and Computation
• An approximation algorithm for scheduling malleable tasks under general precedence constraints
• scientific article; zbMATH DE number 1241387
• A \(\frac 54\)-approximation algorithm for scheduling identical malleable tasks
• APPROXIMATION ALGORITHMS FOR SCHEDULING MALLEABLE TASKS UNDER PRECEDENCE CONSTRAINTS
• scientific article; zbMATH DE number 1875414
• Approximation and Online Algorithms
• scientific article; zbMATH DE number 1947422
• Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme
• scientific article; zbMATH DE number 1863269

Cites work

• M^-convexity and its applications in operations
• A \frac32‐Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks
• Approximating Nash social welfare under rado valuations
• Approximation algorithms for scheduling parallel jobs
• Approximation algorithms for scheduling unrelated parallel machines
• Complexity of Scheduling Parallel Task Systems
• Computing Walrasian equilibria: fast algorithms and structural properties
• Discrete Convex Analysis
• Gross substitutability: an algorithmic survey
• scientific article; zbMATH DE number 7650084 (Why is no real title available?)
• Job Matching, Coalition Formation, and Gross Substitutes
• Linear-Time approximation schemes for scheduling malleable parallel tasks
• Matrices and matroids for systems analysis
• Scheduling cleaning activities on trains by minimizing idle times
• Strong LP formulations for scheduling splittable jobs on unrelated machines
• The Santa Claus problem
• Walrasian equilibrium with gross substitutes

Cited in

(2)

• Malleable scheduling beyond identical machines
• An improved approximation algorithm for scheduling monotonic moldable tasks

This page was built for publication: A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds

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