Repository: DepositOnce â€“ institutional repository for research data and publications of TU Berlin https://depositonce.tu-berlin.de
TY - RPRT
AU - Skutella, Martin
PY - 2000
TI - Approximating the single source unsplittable min-cost flow problem
DO - 10.14279/depositonce-14730
UR - http://dx.doi.org/10.14279/depositonce-14730
PB - Technische UniversitÃ¤t Berlin
LA - en
AB - In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path and the total cost must not exceed a given budget. This problem has been introduced by Kleinberg and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing and virtual-circuit routing.
KW - approximation algorithms
KW - graph algorithms
KW - network flow
KW - routing
ER -