IDEAS home Printed from https://ideas.repec.org/a/ids/ijores/v20y2014i2p226-239.html
   My bibliography  Save this article

An approximation algorithm for discrete minimum cost flows over time problem

Author

Listed:
  • Reza Rostami
  • Ali Ebrahimnejad

Abstract

Ford and Fulkerson around 50 years ago introduced flows over time by adding time dimension to the traditional network flow model. Road and air traffic control, production systems, communication networks (e.g., the internet) and financial flows are examples of this subject. What distinguishes flows over time from the traditional model is transit time on every arc which specifies the amount of time, flow units need to traverse the arc. In this model, flow rate entering an arc may change over time. One of the problems arising in this issue is the minimum cost flow over time problem which aims to determine an s-t flow over time f that satisfies demand d within given time horizon T at minimum cost. It is already shown that this problem is NP-hard, thus as usual a fair amount of study devoted to finding an efficient approximation algorithm for this issue. In this paper, we introduce an approximation algorithm for the T-length bounded discrete minimum cost flows over time problem.

Suggested Citation

  • Reza Rostami & Ali Ebrahimnejad, 2014. "An approximation algorithm for discrete minimum cost flows over time problem," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 20(2), pages 226-239.
    • Handle: RePEc:ids:ijores:v:20:y:2014:i:2:p:226-239
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=61773
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ids:ijores:v:20:y:2014:i:2:p:226-239. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sarah Parker (email available below). General contact details of provider: http://www.inderscience.com/browse/index.php?journalID=170 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.