Worcester Polytechnic Institute Electronic Theses and Dissertations Collection

Title page for ETD etd-042910-160853


Document Typemasters report
Author NameNahabedian, Aaron Joseph
URNetd-042910-160853
TitleA Primal-Dual Approximation Algorithm for the Concurrent Flow Problem
DegreeMS
DepartmentMathematical Sciences
Advisors
  • William Martin, Advisor
  • Keywords
  • approximation algorithm
  • network flow
  • Date of Presentation/Defense2010-04-29
    Availability unrestricted

    Abstract

    The multicommodity flow problem involves shipping multiple commodities simultaneously through a network so that the total flow over each edge does not exceed the capacity of that edge. The concurrent flow problem also associates with each commodity a demand, and involves finding the maximum fraction z, such that z of each commodity’s demand can be feasibly shipped through the network. This problem has applications in message routing, transportation, and scheduling problems. It can be formulated as a linear programming problem, and the best known solutions take advantage of decomposition techniques for linear programming. Often, quickly finding an approximate solution is more important than finding an optimal solution. A solution is epsilon-optimal if it lies within a factor of (1+epsilon) of the optimal solution. We present a combinatorial approximation algorithm for the concurrent flow problem. This algorithm consists of finding an initial flow, and gradually rerouting this flow from more to less congested paths, until an epsilon-optimal flow is achieved. This algorithm theoretically runs much faster than linear programming based algorithms.

    Files
  • nahabedian.pdf

  • Browse by Author | Browse by Department | Search all available ETDs

    [WPI] [Library] [Home] [Top]

    Questions? Email etd-questions@wpi.edu
    Maintained by webmaster@wpi.edu