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

DOI10.1007/S10107-023-02054-ZMaRDI QIDQ6589760zbMATH OpenFDO

Authors Dimitris Fotakis, Jannik Matuschke, Orestis Papadigenopoulos

Publication date 20 August 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites work

• A $\frac32$‐Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks
• A Note on Kelso and Crawford's Gross Substitutes Condition
• Approximating Nash social welfare under rado valuations
• Approximation algorithms for scheduling parallel jobs
• Approximation algorithms for scheduling unrelated parallel machines
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of Scheduling Parallel Task Systems
• Computing Walrasian equilibria: fast algorithms and structural properties
• Discrete Convex Analysis
• Gross substitutability: an algorithmic survey
• Job Matching, Coalition Formation, and Gross Substitutes
• Linear-Time approximation schemes for scheduling malleable parallel tasks
• Polynomial-time approximation schemes for maximizing gross substitutes utility under budget constraints
• 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
• \(M\)-convex function on generalized polymatroid

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 Q6589760)