Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems
| Title | Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems |
| Publication Type | Conference Papers |
| Year of Publication | 1997 |
| Authors | Srinivasan A |
| Conference Name | , 38th Annual Symposium on Foundations of Computer Science, 1997. Proceedings |
| Date Published | 1997/10/20/22 |
| Publisher | IEEE |
| ISBN Number | 0-8186-8197-7 |
| Keywords | Approximation algorithms, Bandwidth, Channel allocation, computational complexity, Computer science, edge-disjoint paths, graph theory, High speed integrated circuits, IEL, Image motion analysis, Information systems, multi-commodity flow relaxation, Multiprocessor interconnection networks, network routing, Optical fiber networks, Routing, routing problems, unsplittable flow |
| Abstract | We present improved approximation algorithms for a family of problems involving edge-disjoint paths and unsplittable flow, and for some related routing problems. The central theme of all our algorithms is the underlying multi-commodity flow relaxation |
| DOI | 10.1109/SFCS.1997.646130 |