Approximation algorithms for maximum weighted throughput on unrelated machines

DOI10.1016/J.TCS.2025.115258MaRDI QIDQ6985824zbMATH OpenFDO

Authors George Karakostas, Stavros G. Kolliopoulos

Publication date 12 May 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115258

zbMATH Keywords

approximation algorithmmaximum weighted throughputPTASschedulingunrelated machines

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Cites work

• O(1/) is the answer in online weighted throughput maximization
• A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• A unified approach to approximating resource allocation and scheduling
• Approximating the throughput of multiple machines in real-time scheduling
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Approximation schemes for a class of subset selection problems
• Breaking 1-1/e barrier for nonpreemptive throughput maximization
• Dependent rounding and its applications to approximation algorithms
• Eliminating migration in multi-processor scheduling
• Geometry meets vectors: approximation algorithms for multidimensional packing
• scientific article; zbMATH DE number 3873052 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7765369 (Why is no real title available?)
• Improvements in throughout maximization for real-time scheduling
• Online Throughput Maximization on Unrelated Machines: Commitment is No Burden
• Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
• Reducibility among combinatorial problems
• Throughput scheduling with equal additive laxity
• Tight approximation algorithms for maximum separable assignment problems

This page was built for publication: Approximation algorithms for maximum weighted throughput on unrelated machines

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