COIN-OR::LEMON - Graph Library

Opened 8 years ago

Last modified 8 years ago

#296 assigned task

Multicommodity flow algorithms

Reported by: kpeter Owned by: kpeter
Priority: major Milestone:
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

It would be important to implement various multicommodity flow algorithms in LEMON. Approximation (and maybe exact) solution methods for fractional, integral and unsplittable multicommodity flow problems.

Change History (3)

comment:1 Changed 8 years ago by kpeter

I'm working on approximation algorithms for the following (fractional) problems according to Garg, Könemann and Fleischer.

  • maximum multicommodity flow,
  • weighted maximum multicommodity flow,
  • maximum concurrent flow,
  • min. cost maximum concurrent flow.

The working repository of these algorithms can be found here:
http://lime.cs.elte.hu/~kpeter/hgwebdir.cgi/lemon-multicommodity/

comment:2 Changed 8 years ago by kpeter

  • Milestone LEMON 1.2 release deleted
  • Owner changed from alpar to kpeter
  • Status changed from new to assigned

comment:3 Changed 8 years ago by kpeter

  • Type changed from enhancement to task
Note: See TracTickets for help on using tickets.