Concepedia

On complexity, representation and approximation of integral multicommodity flows

Anand Srivastav, Peter Stangier

Discrete Applied Mathematics · 2000 · 11 citations · 14 references

DOI

Concepts

References

14

On the Complexity of Timetable and Multicommodity Flow Problems

Shimon Even, Alon Itai, Adi Shamir · SIAM Journal on Computing · 1976 · 1.1K citations

, , +16

Randomized rounding: A technique for provably good algorithms and algorithmic proofs

Prabhakar Raghavan, Clark D. Tompson · COMBINATORICA · 1987 · 1K citations

, , +10

Fast probabilistic algorithms for hamiltonian circuits and matchings

Dana Angluin, Leslie G. Valiant · Journal of Computer and System Sciences · 1979 · 586 citations

, , +16

Faster and simpler algorithms for multicommodity flow and other fractional packing problems

Naveen Garg, Jochen Könemann · 2002 · 574 citations

, , +14

Probabilistic construction of deterministic algorithms: Approximating packing integer programs

Prabhakar Raghavan · Journal of Computer and System Sciences · 1988 · 552 citations

, , +13