Median linear orders: Heuristics and a branch and bound algorithm (Q582183)

The first part of this paper illustrates the relationship between median linear orders and the so-called minimum arc set problem. In the second part a heuristic is studied to solve the minimum feedback arc set problem for non-weighed tournaments, which is then extended to the general case (weighed tournaments). In the last part, a branch and bound (b \& b) method is designed to get all median linear orders associated with a profile of linear orders. Among the advantages of the b \& b method are: (1) whereas most methods are only able to compute just one median linear order, b \& b computes all of them; (2) b \& b always provides exact integer solutions; (3) the algorithm for the b \& b method can be easily set up on any microcomputer for reasonable sized data.