A Quasi-Polynomial Approximation for the Restricted Assignment Problem

DOI10.1137/19M128257XzbMath1495.90072OpenAlexW3095593924MaRDI QIDQ5138780

Lars Rohwedder, Klaus Jansen

Publication date: 4 December 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/19m128257x

zbMATH Keywords

schedulingapproximationlocal searchunrelated machinesintegrality gap

Mathematics Subject Classification ID

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

Related Items (1)

Resource time-sharing for IoT applications with deadlines

Cites Work

• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• The Santa Claus problem
• The Design of Approximation Algorithms
• Santa claus meets hypergraph matchings
• Santa Claus Schedules Jobs on Unrelated Machines
• Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• A Tale of Santa Claus, Hypergraphs and Matroids
• Lazy Local Search Meets Machine Scheduling
• On (1,∊)-Restricted Assignment Makespan Minimization
• Estimating The Makespan of The Two-Valued Restricted Assignment Problem

This page was built for publication: A Quasi-Polynomial Approximation for the Restricted Assignment Problem