Advertisement
Published in:
2017 | OriginalPaper | Chapter
Structured Instances of Restricted Assignment with Two Processing Times
Authors : Klaus Jansen, Lars Rohwedder
Published in: Algorithms and Discrete Applied Mathematics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
For the Restricted Assignment Problem the best known polynomial algorithm is a 2-approximation by Lenstra, Shmoys and Tardos [7]. Even for the case with only two different processing times the ratio above has merely been improved by a tiny margin [2].
In some cases where the restrictions on one or both job sizes are somewhat structured, simple combinatorial algorithms are known that provide better approximation ratios than the algorithm above.
In this paper we study two classes of structured restrictions, that we refer to as the Inclusion Chain Class and the Two Partition Class. We present a 1.5-approximation for each of them.