[Lemon-devel] Regarding the implementation of Cancel & Tighten

[Kovács Péter]

Dear Paul,

You are right, we do not apply dynamic trees in the cancel-and-tighten 
algorithm. There are two major reasons for that. First, this algorithm 
turned out to be rather slow compared to the fastest algorithms (as you 
cited), although it is by far the fastest among our cycle-canceling 
implementations. Second, despite their significant theoretical 
improvement, dynamic trees typically have relatively poor performance in 
practice, just like e.g. Fibonacci heaps (due to the large constant 
factors in the running time of their operations). Therefore, we do not 
expect that their usage can singnificantly improve the practical running 
time of the cancel-and-tighten algorithm on typical problem instances.

You may be interested in the paper "Dynamic Trees in Practice" by Tarjan 
and Werneck:
http://www.cs.princeton.edu/~rwerneck/docs/TW07.pdf

Moreover, let me draw your attention to our detailed paper (instead of 
the conference paper you cited):
https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/Citations/Kiraly-Kovacs_min_cost_flow_ACTA_INFO_2012.pdf

Best regards,
Peter



On 2012.11.12. 19:58, Paul Swoboda wrote:
> Dear developers,
>
> I have lately been interested in cancel and tighten algorithms for
> minimum cost network flow problems. I have checked your implementation
> as well as the benchmark paper "An Experimental Study of Minimum Cost
> Flow Algorithms" by Zoltán Királya and Péter Kovács, where cancel and
> tighten did not fare very favourably, compared to network simplex and
> cost scaling algorithms. After looking into the source code, it seems
> that starting at line 987 in cycle_cancelling.h, version lemon-1.2.3,
> you do not use dynamic trees for canceling cycles as proposed in
> "Finding Minimum-Cost Circulations by Canceling Negative Cycles" by
> Goldberg and Tarjan. Is there a specific reason for this? I would be
> very interested in the possibility to accelerate the algorithm in practice.
>
> Best regards,
>
> Paul Swoboda
> _______________________________________________
> Lemon-devel mailing list
> Lemon-devel at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-devel
>