Ulrich M. Schwarz

  1. A PTAS for Scheduling with Tree Assignment Restrictions.

    Authors: Ulrich M. Schwarz
    Subjects: Data Structures and Algorithms
    Abstract

    Scheduling with assignment restrictions is an important special case of
    scheduling unrelated machines which has attracted much attention in the recent
    past. While a lower bound on approximability of 3/2 is known for its most
    general setting, subclasses of the problem admit polynomial-time approximation
    schemes. This note provides a PTAS for tree-like hierarchical structures,
    improving on a recent 4/3-approximation by Huo and Leung.

Syndicate content