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

Ignore:
Timestamp:
03/01/13 17:59:08 (12 years ago)
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

Unmodified
Removed
• ## doc/groups.dox

 r1003 \image latex planar.eps "Plane graph" width=\textwidth */ /** @defgroup tsp Traveling Salesman Problem @ingroup algs \brief Algorithms for the symmetric traveling salesman problem This group contains basic heuristic algorithms for the the symmetric \e traveling \e salesman \e problem (TSP). Given an \ref FullGraph "undirected full graph" with a cost map on its edges, the problem is to find a shortest possible tour that visits each node exactly once (i.e. the minimum cost Hamiltonian cycle). These TSP algorithms are intended to be used with a \e metric \e cost \e function, i.e. the edge costs should satisfy the triangle inequality. Otherwise the algorithms could yield worse results. LEMON provides five well-known heuristics for solving symmetric TSP: - \ref NearestNeighborTsp Neareast neighbor algorithm - \ref GreedyTsp Greedy algorithm - \ref InsertionTsp Insertion heuristic (with four selection methods) - \ref ChristofidesTsp Christofides algorithm - \ref Opt2Tsp 2-opt algorithm \ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest solution methods. Furthermore, \ref InsertionTsp is usually quite effective. \ref ChristofidesTsp is somewhat slower, but it has the best guaranteed approximation factor: 3/2. \ref Opt2Tsp usually provides the best results in practice, but it is the slowest method. It can also be used to improve given tours, for example, the results of other algorithms. \image html tsp.png \image latex tsp.eps "Traveling salesman problem" width=\textwidth */ /**
• ## doc/groups.dox

 r1036 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. In general NetworkSimplex is the most efficient implementation, but in special cases other algorithms could be faster. In general, \ref NetworkSimplex and \ref CostScaling are the most efficient implementations. \ref NetworkSimplex is usually the fastest on relatively small graphs (up to several thousands of nodes) and on dense graphs, while \ref CostScaling is typically more efficient on large graphs (e.g. hundreds of thousands of nodes or above), especially if they are sparse. However, other algorithms could be faster in special cases. For example, if the total supply and/or capacities are rather small, CapacityScaling is usually the fastest algorithm (without effective scaling). \ref CapacityScaling is usually the fastest algorithm (without effective scaling). These classes are intended to be used with integer-valued input data (capacities, supply values, and costs), except for \ref CapacityScaling, which is capable of handling real-valued arc costs (other numerical data are required to be integer). */ This group contains the algorithms for finding minimum mean cycles \ref clrs01algorithms, \ref amo93networkflows. \ref amo93networkflows, \ref karp78characterization. The \e minimum \e mean \e cycle \e problem is to find a directed cycle LEMON contains three algorithms for solving the minimum mean cycle problem: - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, \ref dasdan98minmeancycle. - \ref KarpMmc Karp's original algorithm \ref karp78characterization. - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved version of Karp's algorithm \ref dasdan98minmeancycle. version of Karp's algorithm \ref hartmann93finding. - \ref HowardMmc Howard's policy iteration algorithm \ref dasdan98minmeancycle. In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the \ref dasdan98minmeancycle, \ref dasdan04experimental. In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the most efficient one, though the best known theoretical bound on its running time is exponential. /** @defgroup planar Planarity Embedding and Drawing @defgroup planar Planar Embedding and Drawing @ingroup algs \brief Algorithms for planarity checking, embedding and drawing
Note: See TracChangeset for help on using the changeset viewer.