Changeset - r879:25804ef35064
« 878:4b1b37
880:0643a9 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Add citations to the scaling MCF algorithms (#180, #184) and improve the doc of their group.
0 3 0
default
3 files changed with 12 insertions and 11 deletions:
doc/groups.dox
6
8
lemon/capacity_scaling.h
2
1
lemon/cost_scaling.h
4
2
↑ Collapse diff ↑
doc/groups.dox
Show white space 12 line context
... ... 
@@ -403,21 +403,19 @@
403 403 
problem and its dual solution, see \ref min_cost_flow
404 404 
"Minimum Cost Flow Problem".
405 405 

			




	406
	406
	
		
LEMON contains several algorithms for this problem.


			




	407
	407
	
		
 - \ref NetworkSimplex Primal Network Simplex algorithm with various


			




	408
	408
	
		
   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.


			




	409
	
	
		
 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on


			




	410
	
	
		
   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,


			




	
	409
	
		
 - \ref CostScaling Cost Scaling algorithm based on push/augment and


			




	
	410
	
		
   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,


			




	411
	411
	
		
   \ref bunnagel98efficient.


			




	412
	
	
		
 - \ref CapacityScaling Successive Shortest %Path algorithm with optional


			




	413
	
	
		
   capacity scaling \ref edmondskarp72theoretical.


			




	414
	
	
		
 - \ref CancelAndTighten The Cancel and Tighten algorithm


			




	415
	
	
		
   \ref goldberg89cyclecanceling.


			




	416
	
	
		
 - \ref CycleCanceling Cycle-Canceling algorithms


			




	417
	
	
		
   \ref klein67primal, \ref goldberg89cyclecanceling.


			




	
	412
	
		
 - \ref CapacityScaling Capacity Scaling algorithm based on the successive


			




	
	413
	
		
   shortest path method \ref edmondskarp72theoretical.


			




	
	414
	
		
 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are


			




	
	415
	
		
   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.


			




	418
	416
	
		

			




	419
	417
	
		
In general NetworkSimplex is the most efficient implementation,


			




	420
	418
	
		
but in special cases other algorithms could be faster.


			




	421
	419
	
		
For example, if the total supply and/or capacities are rather small,


			




	422
	420
	
		
CapacityScaling is usually the fastest algorithm (without effective scaling).


			




	423
	421
	
		
*/

			




        

    

    

    

        

            

                

                    lemon/capacity_scaling.h
                

                

                  
                  
                  
                  Show white space
                  12 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -63,13 +63,14 @@


			




	63
	63
	
		

			




	64
	64
	
		
  /// \brief Implementation of the Capacity Scaling algorithm for


			




	65
	65
	
		
  /// finding a \ref min_cost_flow "minimum cost flow".


			




	66
	66
	
		
  ///


			




	67
	67
	
		
  /// \ref CapacityScaling implements the capacity scaling version


			




	68
	68
	
		
  /// of the successive shortest path algorithm for finding a


			




	69
	
	
		
  /// \ref min_cost_flow "minimum cost flow". It is an efficient dual


			




	
	69
	
		
  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,


			




	
	70
	
		
  /// \ref edmondskarp72theoretical. It is an efficient dual


			




	70
	71
	
		
  /// solution method.


			




	71
	72
	
		
  ///


			




	72
	73
	
		
  /// Most of the parameters of the problem (except for the digraph)


			




	73
	74
	
		
  /// can be given using separate functions, and the algorithm can be


			




	74
	75
	
		
  /// executed using the \ref run() function. If some parameters are not


			




	75
	76
	
		
  /// specified, then default values will be used.

			




        

    

    

    

        

            

                

                    lemon/cost_scaling.h
                

                

                  
                  
                  
                  Show white space
                  12 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -87,14 +87,16 @@


			




	87
	87
	
		
  /// @{


			




	88
	88
	
		

			




	89
	89
	
		
  /// \brief Implementation of the Cost Scaling algorithm for


			




	90
	90
	
		
  /// finding a \ref min_cost_flow "minimum cost flow".


			




	91
	91
	
		
  ///


			




	92
	92
	
		
  /// \ref CostScaling implements a cost scaling algorithm that performs


			




	93
	
	
		
  /// push/augment and relabel operations for finding a minimum cost


			




	94
	
	
		
  /// flow. It is an efficient primal-dual solution method, which


			




	
	93
	
		
  /// push/augment and relabel operations for finding a \ref min_cost_flow


			




	
	94
	
		
  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,


			




	
	95
	
		
  /// \ref goldberg97efficient, \ref bunnagel98efficient. 


			




	
	96
	
		
  /// It is a highly efficient primal-dual solution method, which


			




	95
	97
	
		
  /// can be viewed as the generalization of the \ref Preflow


			




	96
	98
	
		
  /// "preflow push-relabel" algorithm for the maximum flow problem.


			




	97
	99
	
		
  ///


			




	98
	100
	
		
  /// Most of the parameters of the problem (except for the digraph)


			




	99
	101
	
		
  /// can be given using separate functions, and the algorithm can be


			




	100
	102
	
		
  /// executed using the \ref run() function. If some parameters are not


			




        

    






    
    



    


    

     
    
0 comments (0 inline)