COIN-OR::LEMON - Graph Library

Changeset 1038:a2d142bb5d3c in lemon-main for doc/groups.dox


Ignore:
Timestamp:
03/01/13 17:59:08 (12 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
1030:4936be66d2f5 (diff), 1037:d3dcc49e6403 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge #386

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r1003 r1038  
    559559\image latex planar.eps "Plane graph" width=\textwidth
    560560*/
     561 
     562/**
     563@defgroup tsp Traveling Salesman Problem
     564@ingroup algs
     565\brief Algorithms for the symmetric traveling salesman problem
     566
     567This group contains basic heuristic algorithms for the the symmetric
     568\e traveling \e salesman \e problem (TSP).
     569Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     570the problem is to find a shortest possible tour that visits each node exactly
     571once (i.e. the minimum cost Hamiltonian cycle).
     572
     573These TSP algorithms are intended to be used with a \e metric \e cost
     574\e function, i.e. the edge costs should satisfy the triangle inequality.
     575Otherwise the algorithms could yield worse results.
     576
     577LEMON provides five well-known heuristics for solving symmetric TSP:
     578 - \ref NearestNeighborTsp Neareast neighbor algorithm
     579 - \ref GreedyTsp Greedy algorithm
     580 - \ref InsertionTsp Insertion heuristic (with four selection methods)
     581 - \ref ChristofidesTsp Christofides algorithm
     582 - \ref Opt2Tsp 2-opt algorithm
     583
     584\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     585solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     586
     587\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     588approximation factor: 3/2.
     589
     590\ref Opt2Tsp usually provides the best results in practice, but
     591it is the slowest method. It can also be used to improve given tours,
     592for example, the results of other algorithms.
     593
     594\image html tsp.png
     595\image latex tsp.eps "Traveling salesman problem" width=\textwidth
     596*/
    561597
    562598/**
  • doc/groups.dox

    r1036 r1038  
    407407   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    408408
    409 In general NetworkSimplex is the most efficient implementation,
    410 but in special cases other algorithms could be faster.
     409In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     410implementations.
     411\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
     412several thousands of nodes) and on dense graphs, while \ref CostScaling is
     413typically more efficient on large graphs (e.g. hundreds of thousands of
     414nodes or above), especially if they are sparse.
     415However, other algorithms could be faster in special cases.
    411416For example, if the total supply and/or capacities are rather small,
    412 CapacityScaling is usually the fastest algorithm (without effective scaling).
     417\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
     418
     419These classes are intended to be used with integer-valued input data
     420(capacities, supply values, and costs), except for \ref CapacityScaling,
     421which is capable of handling real-valued arc costs (other numerical
     422data are required to be integer).
    413423*/
    414424
     
    449459
    450460This group contains the algorithms for finding minimum mean cycles
    451 \ref clrs01algorithms, \ref amo93networkflows.
     461\ref amo93networkflows, \ref karp78characterization.
    452462
    453463The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     
    465475
    466476LEMON contains three algorithms for solving the minimum mean cycle problem:
    467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
    468   \ref dasdan98minmeancycle.
     477- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
    469478- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    470   version of Karp's algorithm \ref dasdan98minmeancycle.
     479  version of Karp's algorithm \ref hartmann93finding.
    471480- \ref HowardMmc Howard's policy iteration algorithm
    472   \ref dasdan98minmeancycle.
    473 
    474 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     481  \ref dasdan98minmeancycle, \ref dasdan04experimental.
     482
     483In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
    475484most efficient one, though the best known theoretical bound on its running
    476485time is exponential.
     
    540549
    541550/**
    542 @defgroup planar Planarity Embedding and Drawing
     551@defgroup planar Planar Embedding and Drawing
    543552@ingroup algs
    544553\brief Algorithms for planarity checking, embedding and drawing
Note: See TracChangeset for help on using the changeset viewer.