Establishes no-PTAS hardness for interval-restricted assignment and approximation thresholds of 48/47 and 1.5 for 2- and 4-resource restricted scheduling.
Graph Balancing with Two Edge Types
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In the graph balancing problem the goal is to orient a weighted undirected graph to minimize the maximum weighted in-degree. This special case of makespan minimization is NP-hard to approximate to a factor better than 3/2 even when there are only two types of edge weights. In this note we describe a simple 3/2 approximation for the graph balancing problem with two-edge types, settling this very special case of makespan minimization.
fields
cs.CC 1years
2019 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Inapproximability Results for Scheduling with Interval and Resource Restrictions
Establishes no-PTAS hardness for interval-restricted assignment and approximation thresholds of 48/47 and 1.5 for 2- and 4-resource restricted scheduling.