A note on graph balancing problems with restrictions

作者：Lee Kangbok; Leung Joseph Y T^*; Pinedo Michael L

来源：Information Processing Letters, 2009, 110(1): 24-29.

DOI：10.1016/j.ipl.2009.09.015

• Approximation algorithm
• Combinatorial problems
• Computational complexity
• Graph balancing
• Parallel machines scheduling
• Eligibility constraints
• Fully polynomial time approximation scheme (FPTAS)

We consider the graph balancing problem of providing orientations to edges in an undirected multi-graph to minimize the maximum load. We first obtain an FPTAS when the multi-graph is restricted to a tree. We also obtain some additional results for other restricted cases by showing equivalencies with related combinatorial problems.

• 出版日期2009-12-1