Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs

DOI10.4230/lipics.isaac.2020.14OpenAlexW3117847431MaRDI QIDQ6065410

Jörg Rothe, Trung Thanh Nguyen

Publication date: 14 November 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/13358/pdf/LIPIcs-ISAAC-2020-14.pdf/

zbMATH Keywords

machine schedulingpolynomial-time approximation algorithmload balancingbi-criteria approximation algorithm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints

Cites Work

• Unnamed Item
• Unnamed Item
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines
• Approximation algorithms for scheduling unrelated parallel machines
• Approximation schemes for scheduling on parallel machines
• An approximation algorithm for the generalized assignment problem
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• A property of assignment type mixed integer linear programming problems
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• A unified framework for designing EPTAS for load balancing on parallel machines
• Approximation schemes for scheduling and covering on unrelated machines
• Improved approximation schemes for scheduling unrelated parallel machines
• Integer Programming with a Fixed Number of Variables
• All-Norm Approximation Algorithms
• Convex programming for scheduling unrelated parallel machines
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Modeling Facility Location Problems as Generalized Assignment Problems
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• On Allocating Goods to Maximize Fairness
• A PTAS for Scheduling Unrelated Machines of Few Different Types
• An EPTAS for scheduling on unrelated machines of few different types

This page was built for publication: Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs