A Natural Randomization Strategy for Multicommodity Flow and Related Algorithms

Abstract

We consider the approximation algorithm of Leighton et. al. for the multicommodity flow problem. We give a more natural randomization strategy that is simpler than the one in the original algorithm and results in a better running time. This strategy also applies to several related algorithms.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1991
Accession Number
ADA254368

Entities

People

  • Andrew V. Goldberg

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Commodities
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Congestion
  • Iterations
  • Linear Programming
  • Mathematics
  • Notation
  • Optimization
  • Polynomials
  • Precision
  • Universities

Readers

  • Operations Research
  • Regression Analysis.