COIN-OR::LEMON - Graph Library

Opened 10 years ago

Last modified 9 years ago

#296 assigned task

Multicommodity flow algorithms

Reported by: Peter Kovacs Owned by: Peter Kovacs
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 10 years ago by Peter Kovacs

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 9 years ago by Peter Kovacs

Milestone: LEMON 1.2 release
Owner: changed from Alpar Juttner to Peter Kovacs
Status: newassigned

comment:3 Changed 9 years ago by Peter Kovacs

Type: enhancementtask
Note: See TracTickets for help on using tickets.