Efficient algorithms for separated continuous linear programs: The multicommodity flow problem with holding costs and extensions

• 成果类型: Article
• 署名作者: Fleischer, L
• 署名单位: International Business Machines (IBM); IBM USA; Columbia University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1050.0166
• 发表日期: 2005
• 页码: 916-938
• 关键词: practical algorithms; stochastic networks; fluid relaxations; makespan; tracking; policies

摘要

We give an approximation scheme for separated continuous linear programming problems. Such problems arise as fluid relaxations of multiclass queueing networks and are used to find approximate solutions to complex job shop scheduling problems. In a network with linear flow costs and linear, per-unit-time holding costs, our algorithm finds a drainage of the network that, for given constants epsilon > 0 and delta > 0, has total cost (1 + epsilon)OPT + delta, where OPT is the cost of the minimum cost drainage. The complexity of our algorithm is polynomial in the size of the input network, 1/epsilon, and log(1/delta). The fluid relaxation is a continuous problem. While the problem is known to have a piecewise constant solution, it is not known to have a polynomially sized solution. We introduce a natural discretization of polynomial size and prove that this discretization produces a solution with low cost. This is the first polynomial time algorithm with a provable approximation guarantee for fluid relaxations.