IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v77y2013i3p381-391.html
   My bibliography  Save this article

A polynomial time approximation algorithm for the two-commodity splittable flow problem

Author

Listed:
  • Elke Eisenschmidt
  • Utz-Uwe Haus

Abstract

We consider a generalization of the unsplittable maximum two-commodity flow problem on undirected graphs where each commodity $${i \in \{1, 2\}}$$ can be split into a bounded number k i of equally-sized chunks that can be routed on different paths. We show that in contrast to the single-commodity case this problem is NP-hard, and hard to approximate to within a factor of α > 1/2. We present a polynomial time 1/2-approximation algorithm for the case of uniform chunk size over both commodities and show that for even k i and a mild cut condition it can be modified to yield an exact method. The uniform case can be used to derive a 1/4-approximation for the maximum concurrent (k 1 , k 2 )-splittable flow without chunk size restrictions for fixed demand ratios. Copyright Springer-Verlag 2013

Suggested Citation

  • Elke Eisenschmidt & Utz-Uwe Haus, 2013. "A polynomial time approximation algorithm for the two-commodity splittable flow problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 77(3), pages 381-391, June.
    • Handle: RePEc:spr:mathme:v:77:y:2013:i:3:p:381-391
    DOI: 10.1007/s00186-012-0402-9
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00186-012-0402-9
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s00186-012-0402-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

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

    References listed on IDEAS

    as
    1. T. C. Hu, 1963. "Multi-Commodity Network Flows," Operations Research, INFORMS, vol. 11(3), pages 344-360, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Natalia Vanetik, 2012. "On the fractionality of the path packing problem," Journal of Combinatorial Optimization, Springer, vol. 24(4), pages 526-539, November.
    2. Sedeno-Noda, A. & Gonzalez-Martin, C. & Gutierrez, J., 2005. "The biobjective undirected two-commodity minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 164(1), pages 89-103, July.
    3. Bertrand Guenin, 2002. "Integral Polyhedra Related to Even-Cycle and Even-Cut Matroids," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 693-710, November.
    4. Lin, Yi-Kuei, 2006. "A simple algorithm to generate all (d,B)-MCs of a multicommodity stochastic-flow network," Reliability Engineering and System Safety, Elsevier, vol. 91(8), pages 923-929.
    5. Lin, Yi-Kuei, 2007. "Reliability of a computer network in case capacity weight varying with arcs, nodes and types of commodity," Reliability Engineering and System Safety, Elsevier, vol. 92(5), pages 646-652.
    6. Lin, Yi-Kuei, 2010. "A stochastic model to study the system capacity for supply chains in terms of minimal cuts," International Journal of Production Economics, Elsevier, vol. 124(1), pages 181-187, March.
    7. Lin, Yi-Kuei, 2007. "Generate upper boundary vectors meeting the demand and budget for a p-commodity network with unreliable nodes," European Journal of Operational Research, Elsevier, vol. 183(1), pages 253-262, November.
    8. Lin, Yi-Kuei, 2007. "Performance evaluation for the logistics system in case that capacity weight varies from arcs and types of commodity," International Journal of Production Economics, Elsevier, vol. 107(2), pages 572-580, June.
    9. Lin, Yi-Kuei, 2007. "On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint," European Journal of Operational Research, Elsevier, vol. 176(1), pages 347-360, January.
    10. Fred Glover & Gary Kochenberger & Moses Ma & Yu Du, 2020. "Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange," 4OR, Springer, vol. 18(4), pages 387-417, December.
    11. Khodakaram Salimifard & Sara Bigharaz, 2022. "The multicommodity network flow problem: state of the art classification, applications, and solution methods," Operational Research, Springer, vol. 22(1), pages 1-47, March.
    12. Yeh, Wei-Chang, 2008. "A simple minimal path method for estimating the weighted multi-commodity multistate unreliable networks reliability," Reliability Engineering and System Safety, Elsevier, vol. 93(1), pages 125-136.
    13. Pengfei Zhang & Neng Fan, 2017. "Analysis of budget for interdiction on multicommodity network flows," Journal of Global Optimization, Springer, vol. 67(3), pages 495-525, March.
    14. Fred Glover & Gary Kochenberger & Moses Ma & Yu Du, 2022. "Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange," Annals of Operations Research, Springer, vol. 314(1), pages 185-212, July.
    15. A. Ouorou & P. Mahey & J.-Ph. Vial, 2000. "A Survey of Algorithms for Convex Multicommodity Flow Problems," Management Science, INFORMS, vol. 46(1), pages 126-147, January.
    16. Hiroshi Hirai, 2014. "The Maximum Multiflow Problems with Bounded Fractionality," Mathematics of Operations Research, INFORMS, vol. 39(1), pages 60-104, February.
    17. Ali Kakhbod & S. Tabatabaei Yazdi, 2010. "On describing the routing capacity regions of networks," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 72(1), pages 95-106, August.
    18. Myung, Young-Soo & Kim, Hyun-joon, 2004. "A cutting plane algorithm for computing k-edge survivability of a network," European Journal of Operational Research, Elsevier, vol. 156(3), pages 579-589, August.

    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:spr:mathme:v:77:y:2013:i:3:p:381-391. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.