Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
- 1 May 1999
- proceedings article
- Published by Association for Computing Machinery (ACM)
Abstract
No abstract availableThis publication has 10 references indexed in Scilit:
- Approximation Algorithms for Disjoint Paths and Related Routing and Packing ProblemsMathematics of Operations Research, 2000
- On the Inapproximability of Disjoint Paths and Minimum Steiner Forest with Bandwidth ConstraintsJournal of Computer and System Sciences, 2000
- Decision algorithms for unsplittable flow and the half-disjoint paths problemPublished by Association for Computing Machinery (ACM) ,1998
- Primal-dual approximation algorithms for integral flow and multicut in treesAlgorithmica, 1997
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991
- An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Randomized rounding: A technique for provably good algorithms and algorithmic proofsCombinatorica, 1987
- The directed subgraph homeomorphism problemTheoretical Computer Science, 1980
- On the Complexity of Timetable and Multicommodity Flow ProblemsSIAM Journal on Computing, 1976
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963