Single-source k-splittable min-cost flows |
| |
| Authors: | Fernanda Salazar |
| |
| Institution: | a Escuela Politécnica Nacional, Departamento de Matemática, Quito, Ecuador
b TU Berlin, Institut für Mathematik, MA 5-2, Str. des 17. Juni 136, 10623 Berlin, Germany |
| |
| Abstract: | Motivated by a famous open question on the single-source unsplittable minimum cost flow problem, we present a new approximation result for the relaxation of the problem where, for a given number k, each commodity must be routed along at most k paths. |
| |
| Keywords: | Approximation algorithm Multi-commodity flow Network flow Routing Unsplittable flow k-splittable flow |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
