Approximation Algorithm for A Bicriteria Multicommodity Flow Problem

摘要

In the present work,one of bicriteria multicommodity flow problem,called as Maximum Flow Problem with Minimized Maximum of Met Rates,is proposed to find a certain kind of weak solutions for the operational decisions of many practical situations with multicommodity flow,for instance,the emergency logistics distribution decision stemming from the action of China's reliving the areas suffering the tremendous snow disaster in the beginning of 2008.For the problem,the existence of solutions is proved,a pseudopolynomial time approximation algorithm to solve it is designed,finally an approximation measure on the algorithm we design is proposed and proved.