pith. sign in

arxiv: 1604.06918 · v3 · pith:PDPLO6Y2new · submitted 2016-04-23 · 💻 cs.DS

Graph Balancing with Two Edge Types

Deeparnab Chakrabarty , Kirankumar Shiragur This is my paper
classification 💻 cs.DS
keywords graphbalancingtypescaseedgemakespanminimizationproblem
0
0 comments X
read the original 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.

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.