pith. sign in

arxiv: 1009.4529 · v1 · pith:3SEPLUB6new · submitted 2010-09-23 · 💻 cs.DS

A PTAS for Scheduling with Tree Assignment Restrictions

Ulrich M. Schwarz This is my paper
classification 💻 cs.DS
keywords schedulingapproximationassignmentptasrecentrestrictionsadmitapproximability
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Inapproximability Results for Scheduling with Interval and Resource Restrictions

    cs.CC 2019-07 unverdicted novelty 7.0

    Establishes no-PTAS hardness for interval-restricted assignment and approximation thresholds of 48/47 and 1.5 for 2- and 4-resource restricted scheduling.