solve_LSAP               package:clue               R Documentation

_S_o_l_v_e _L_i_n_e_a_r _S_u_m _A_s_s_i_g_n_m_e_n_t _P_r_o_b_l_e_m

_D_e_s_c_r_i_p_t_i_o_n:

     Solve the linear sum assignment problem using the Hungarian
     method.

_U_s_a_g_e:

     solve_LSAP(x, maximum = FALSE)

_A_r_g_u_m_e_n_t_s:

       x: a square matrix with nonnegative entries.

 maximum: a logical indicating whether to minimize of maximize the sum
          of assigned costs.

_D_e_t_a_i_l_s:

     If n is the number of rows and columns of 'x', 'solve_LSAP' finds
     a permutation 'p' of the numbers from 1 to n such that sum_{i=1}^n
     x[i, p[i]] is minimized or maximized.

     This permutation can be found using a linear program (and package
     'lpSolve' provides a function 'lp.assign' for doing so), but
     typically more efficiently and provably in polynomial time O(n^3)
     using primal-dual methods such as the so-called Hungarian method
     (see the references).

_V_a_l_u_e:

     An object of class '"solve_LSAP"' with the optimal assignment of
     rows to columns.

_A_u_t_h_o_r(_s):

     Walter Böhm Walter.Boehm@wu-wien.ac.at kindly provided C code
     implementing the Hungarian method.

_R_e_f_e_r_e_n_c_e_s:

     C. Papadimitriou and K. Steiglitz (1982) _Combinatorial
     Optimization: Algorithms and Complexity_. Englewood Cliffs:
     Prentice Hall.

_E_x_a_m_p_l_e_s:

     x <- matrix(c(5, 1, 4, 3, 5, 2, 2, 4, 4), nr = 3)
     solve_LSAP(x)
     solve_LSAP(x, max = TRUE)

