A survey on the linear ordering problem for weighted or unweighted tournaments

Adám A (1964) Problem. In: Theory of graphs and its applications. Proc Coll Smolenice, Czech Acad Sci Publ

Adler I, Alon N, Ross SM (2001) On the number of Hamiltonian paths in tournaments. Random Struct Alg 18:291–296

Ailon N, Alon N (2007) Hardness of fully dense problems (submitted)

Ailon N, Charikar M, Newman A (2005) Aggregating inconsistent information: ranking and clustering. In: Proceedings of the 37th annual ACM symposium on Theory of computing (STOC): 684–693

Ali I, Cook WD, Kress M (1986) On the minimum violations ranking of a tournament. Manage Sci 32:660–674

Alon N (1990) The maximum number of Hamiltonian paths in tournaments. Combinatorica 10: 319–324

Alon N (2006) Ranking tournaments. SIAM J Discrete Mathe 20(1):137–142

Alon N, Spencer J (2000) The probabilistic method, 2nd edn. Wiley, New York

Alspach B (1967) Cycles of each length in regular tournaments. Can Math Bull 10:283–286

Alspach B (1968) A combinatorial proof of a conjecture of Goldberg and Moon. Can Math Bull 11:655–661

Arditti D (1984) Un nouvel algorithme de recherche d’un ordre induit par des comparaisons par paires. In: Diday E et al. (eds). Data analysis and informatics III. North Holland, Amsterdam, 323–343

Arora S, Frieze A, Kaplan H (1996) A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS):2433

Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (2003) Complexity and approximation, 2nd edn. Springer, Berlin

Baker FB, Hubert LJ (1977) Applications of combinatorial programming to data analysis: seriation using asymmetric proximity measures. Br L Math Statist Psychol 30:154–164

Banks J (1985) Sophisticated voting outcomes and agenda control. Soc Choice Welfare 2:295–306

Banks J, Bordes G, Le Breton M (1991) Covering relations, closest orderings and hamiltonian bypaths in tournaments. Soc Choice Welfare 8:355–363

Barbut M (1966) Note sur les ordres totaux à distance minimum d’une relation binaire donnée. Mathématiques et Sciences humaines 17:47–48

Bar-Noy A, Naor J (1990) Sorting, minimal feedback sets, and Hamilton paths in tournaments. SIAM J Disc Math 3(1):7–20

Barthélemy J-P, Monjardet B (1981) The median procedure in cluster analysis and social choice theory. Math Soc Sci 1:235–267

Barthélemy J-P, Monjardet B (1988) The median procedure in data analysis: new results and open problems. In: Bock HH (ed) Classification and related methods of data analysis. North Holland, Amsterdam

Barthélemy J-P, Guénoche A, Hudry O (1989) Median linear orders: heuristics and a branch and bound algorithm. EJOR 41:313–325

Barthélemy J-P, Hudry O, Isaak G, Roberts FS, Tesman B (1995) The reversing number of a digraph. Discrete Appl Math 60:39–76

Barthélemy J-P, Cohen G, Lobstein A (1996) Algorithmic Complexity and Communication Problems. UCL Press, London

Bartholdi III JJ, Tovey CA, Trick MA (1989) Voting schemes for which it can be difficult to tell who won the election. Soc Choice Welfare 6:157–165

Becker O (1967) Das Helmstädtersche Reihenfolgeproblem—die Effizienz verschiedener Näherungsverfahren. In: Computers uses in the Social Science. Vienna

Belloni A, Lucena A (2004) Lagrangian heuristics for the linear ordering problem. In: Resende MGC, de Sousa JP (eds). Metaheuristics: Computer Decision Making. Kluwer Academic Publishers, New York, pp. 37–63

Berge C (1985) Graphs. North-Holland, Amsterdam

Berger B, Shor PW (1990) Approximation algorithms for the maximum acyclic subgraph problem. In: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms (SODA), 236–243

Berger B, Shor PW (1997) Tight bounds for the maximum acyclic subgraph problem. J Algor 25:1–18

Bermond J-C (1972) Ordres à distance minimum d’un tournoi et graphes partiels sans circuits maximaux. Math Sci hum 37:5–25

Bermond J-C (1975) The circuit-hypergraph of a tournament. In: Infinite and finite sets, Proceedings of the Colloquia Mathematica Societatis János Bolyai 10. North Holland, Amsterdam, 165–180

Bermond J-C, Kodratoff Y (1976) Une heuristique pour le calcul de l’indice de transitivité d’un tournoi. RAIRO 10(3):83–92

Bertacco L, Brunetta L, Fischetti M (2004) The linear ordering problem with cumulative costs. Technical report, University of Padova, and EJOR (in press)

Black D (1958) The theory of committees and elections. Cambridge University Press, London

Blin JM, Whinston AB (1974) A note on majority rule under transitivity constraints. Manage Sci 20:1439–1440

Blin JM, Whinston AB (1975) Discriminant functions and majority voting. Manage Sci 21: 1029–1041

Boenchendorf K (1982) Reihenfolgenprobleme/Mean-flow-time sequencing. Mathematical Systems in Economics 74, Verlagsgruppe Athanäum/Hain/Scriptor/Hanstein

Bolotashvili G, Kovalev M, Girlich E (1999) New Facets of the Linear Ordering Polytope. SIAM J Discrete Math 12(3):326–336

Borda J-C (chevalier de) (1784) Mémoire sur les élections au scrutin, Histoire de l’Académie Royale des Sciences pour 1781, Paris

Bowman VJ, Colantoni CS (1973) Majority rule under transitivity constraints. Manage Sci 19: 1029–1041

Brualdi RA, Qiao L (1983) Upsets in round robin tournaments. J Combin Theory 35 Ser B:62–77

Brualdi RA, Qiao L (1984) The interchange graph of tournaments with the same score vector. In: Progress in graph theory. Academic Press, Toronto, pp 129–151

Burkov VN, Groppen VO (1972) Branch cuts in strongly connected graphs and permutation potentials. Auto Remote Control 6:111–119

Campos V, Laguna M, Martí R (1999) Scatter search for the linear ordering problem. In: Corne D, Dorigo M, Glover F (eds). New ideas in optimization. McGraw-Hill, New York, pp. 331–339

Campos V, Glover F, Laguna M, Martí R (2001) An experimental evaluation of a scatter search for the linear ordering problem. J Global Optim 21(4):397–414

Chanas S, Kobylanski P (1996) A new heuristic algorithm solving the linear ordering problem. Comput Optim Appl 6:191–205

Chaovalitwongse W, Pardalos PM (1997) GRASP with Path-Relinking for the Linear Ordering Problem. Industrial and Systems Engineering Working Paper, Rutgers University

Charbit P, Thomasse S, Yeo A (2007) The minimum feedback arc set problem is NP-hard for tournaments. Combin Prob Comput 16(1):1–4

Charon I, Germa A, Hudry O (1992a) Encadrement de l’indice de Slater d’un tournoi à l’aide de ses scores. Math Inf Sci Hum 118:53–68

Charon I, Germa A, Hudry O (1992b) Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois. Math Inf Sci Hum 119:53–74

Charon I, Germa A, Hudry O (1996a) Random generation of tournaments and asymmetric digraphs with given out-degrees. Eur J Oper Res 95:411–419

Charon I, Guénoche A, Hudry O, Woirgard F (1996b) A bonsaï branch and bound method applied to voting theory. In: Ordinal and symbolic data analysis. Springer, Berlin, pp 309–318

Charon I, Hudry O, Woirgard F (1996c) Ordres médians et ordres de Slater des tournois. Mathématiques, Informatique et Sciences humaines 133:23–56

Charon I, Guénoche A, Hudry O, Woirgard F (1997a) New results on the computation of median orders. Disc Math 165–166:139–154

Charon I, Hudry O, Woirgard F (1997b) A 16-vertex tournament for which Banks set and Slater set are disjoint. Disc Appl Math 80(2–3):211–215

Charon I, Hudry O (1998) Lamarckian genetic algorithms applied to the aggregation of preferences. Ann Oper Res 80:281–297

Charon I, Hudry O (2000) Slater orders and Hamiltonian paths of tournaments. Electron Notes Disc Math 5:60–63

Charon I, Hudry O (2001a) The noising methods: a generalization of some metaheuristics. Eur J Oper Res 135(1):86–101

Charon I, Hudry O (2001b) Metod vetvei i granits dlia recheniia zadatchi o lineinom poriadke na vzvechennikh tournirakh. Discretii Analiz i Issledovanie Operatsii 8 (2) Seriia 2:73–91 (in Russian)

Charon I, Hudry O (2002) The noising methods: a survey. In: Hansen P, Ribeiro CC (eds) Essays and surveys in metaheuristics. Kluwer Academic Publishers, Boston, pp. 245–261

Charon I, Hudry O (2003) Links between the Slater index and the Ryser index of tournaments. Graphs Combina 19(3):309–322

Charon I, Hudry O (2006) A branch and bound algorithm to solve the linear ordering problem for weighted tournaments. Disc Appl Math 154:2097–2116

Charon I, Hudry O (2007) Building a mi nimum profile or tournaments or of linear orders from a weighted graph (in preparation)

Chartrand G, Geller D, Hedetniemi S (1971) Graphs with forbidden subgraphs. J Comb Theory 10 (1) series B:12–41

Christof T, Reinelt G (1996) Combinatorial optimization and small polytopes. Top 4(1):1–64

Christof T, Reinelt G (1997a) Low-dimensional Linear Ordering Polytopes. Working paper, University of Heidelberg

Christof T, Reinelt G (1997b) Small instances relaxations for solving linear ordering problems by branch-and-cut. Technical report, University of Heidelberg

Christof T, Reinelt G (2001) Algorithmic aspects of using small instance relaxations in parallel branch-and-cut. Algorithmica 30(4):597–629

Christophe J, Doignon J-P, Fiorini S (2004) The biorder. Order 21/1:61–82

Cohen W, Schapire R, Singer Y (1999) Learning to order things. J Artif Intell Res 10:213–270

Condorcet MJAN, Caritat (marquis de) (1785) Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix, Paris

Congram RK (2000) Polynomially searchable exponential neighbourhoods for sequencing problems in combinatorial optimisation. PhD thesis, University of Southampton

Conitzer V (2005) Computing Slater Rankings Using Similarities Among Candidates. IBM research report RC23748 (W0510–105)

Cook WD, Saipe AL (1976) Committee approach to priority planning: the median ranking method. Cahiers du Centre d’études et de recherche opèrationnelle 18(3):337–352

Cook WD, Golan I, Kress M (1988) Heuristics for ranking players in a round robin tournament. Comput Oper Res 15(2):135–144

Cook WD, Doyle J, Green R, Kress M (1996) Ranking players in multiple tournaments. Comput Oper Res 23(9):869–880

Copeland AH (1951) A “reasonable” social welfare function. Seminar on applications of mathematics to social sciences, University of Michigan

Coppersmith D, Winograd S (1990) Matrix multiplication via arithmetic progressions. J Symbolic Comput 9:251–280

Coppersmith D, Fleischer L, Rudra A (2006) Ordering by weighted number of wins gives a good ranking for weighted tournaments. In: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (SODA’06), pp 776–782

Czygrinow A, Poljak S, Rödl V (1999) Constructive quasi-Ramsey numbers and tournament ranking. SIAM J Disc Math 12(1):48–63

Davenport A, Kalagnanam J (2004) A computational study of the Kemeny rule for preference aggregation. In: Proceedings of the national conference on artificial intelligence (AAAI), pp 697–702

Debord B (1987a) Caractérisation des matrices de préférences nettes et méthodes d’agrégation associées, Mathématiques et Sciences humaines 97:5–17

Debord B (1987b) Axiomatisation de procédures d’agrégation de préférences. PhDthesis, Université scientifique technologique et médicale de Grenoble

de Cani JS (1969) Maximum likelihood paired comparison ranking by linear programming. Biometrika 3:537–545

de Cani JS (1972) A branch and bound algorithm for maximum likelihood paired comparison ranking. Biometrika 59:131–135

de la Vega, WF (1983) On the maximal cardinality of a consistent set of arcs in a random tournament. J Comb Theory 35, series B:328–332

Dixon JD (1967) The maximum order of the group of a tournament. Can Math Bull 10:503–505

Dodgson CL (1876) A method of taking votes on more than two issues, Clarendon Press, Oxford, and in D. Black, The theory of committees and elections, Cambridge University Press, London, 1958

Doignon J-P, Fiorini S, Joret G (2006) Facets of the linear ordering polytope: a unification for the fence family through weighted graphs. J Math Psychol 50/3:251–262

Dom M, Guo J, Hüffner F, Niedermeier R, Truß A (2006) Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments. Lecture Notes in Computer Science 3998, Springer, Heidelberg, pp 320–331

Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin

Dréo J, Petrowski A, Taillard E, Siarry P (2006) Metaheuristics for hard Optimization, Methods and Case Studies. Springer, Berlin

Duarte A, Laguna M, Marti R (2006) Tabu search for the linear ordering problem with cumulative costs, Technical Report, University of Valencia

Dugat V (1990) Décomposition de tournois réguliers : théorie et application aux algorithmes de tests d’isomorphisme. PhD thesis, Université Paul Sabatier, Toulouse

Dutta B (1988) Covering sets and a new Condorcet choice correspondence. J Econ Theory 44(1988):63–80

Dwork C, Kumar R, Naor M, Sivakumar D (2001) Rank aggregation methods for the Web. In: Proceedings of the 10th international conference on World Wide Web (WWW10), pp 613–622

Eades P, Lin X (1995) A new heuristic for the feedback arc set problem. Aust J Comb 12:15–26

Eades P, Lin X, Smyth WF (1993) A fast and effective heuristic for the feedback arc set problem. Inform Process Lett 47(6):319–323

Erdös P, Moser L (1964) On the representation of directed graphs as unions of orderings. Magyar Tud Akad Mat Kutato Int Közl 9:125–132

Erdös P, Moon JW (1965) On sets of consistent arcs in a tournament. Canad Math Bull 8:269–271

Even G, Naor JS, Sudan M, Schieber B (1998) Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20(2):151–174

Fagin R, Kumar R, Mahdian M, Sivakumar D, Vee E (2005) Rank aggregation: an algorithmic perspective. Unpublished Manuscript

Festa P, Pardalos P, Resende M (1999) Feedback set problems. In: handbook of combinatorial optimization 4, Kluwer Academic Publishers, Boston

Fiorini S (2001a) Polyhedral combinatorics of order polytopes. PhD thesis, Université libre de Bruxelles

Fiorini S (2001b) Determining the automorphism group of the linear ordering polytope. Disc Appl Math 112/1–3:121–128

Fiorini S, Fishburn P (2003) Facets of linear signed order polytopes. Disc Appl Math 131/3:597–610

Fiorini S (2006a) How to recycle your facets. Disc Optim 3/2:136–153

Fiorini S (2006b) 0, 1/2-cuts and the linear ordering problem: surfaces that define facets. SIAM J Disc Math 20/4: 893–912

Fishburn P (1977) Condorcet social choice functions. SIAM J Appl Math 33:469–489

Fishburn P (1992) Induced binary probabilities and the linear ordering polytope: a status report. Math Soc Sci 23:67–80

Flood MM (1990) Exact and heuristic algorithms for the weighted feedback arc set problem: a special case of the skew-symmetric quadratic assignment problem. Networks 20:1–23

Flueck JA, Korsh JF (1974) A branch search algorithm for maximum likelihood paired comparison ranking. Biometrika 61(3):621–626

Fulkerson DR (1965) Upsets in round robin tournaments. Can J Math 17:957–969

Gamboa D, Rego C, Glover F (2006) A Relax-and-Cut RAMP Approach for the Linear Ordering Problem. In the abstracts booklet of ECCOXIX/CO2006 Joint Meeting, Porto, Portugal, p. 40

Garcia CG, Perez-Brito D, Campos V, Marti R (2006) Variable neighborhood search for the linear ordering problem. Comput Oper Res 33(12):35493565

Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. Freeman, New York

Girlich E, Kovalev M, Nalivaiko V (1998) A note on the extension of facet-defining digraphs. Technical report 23/98, Faculty of Mathematics, University of Magdeburg

Glover F, Kochenberger GA (2003) Handbook of Metaheuristics. Kluwer Academic Publishers, Boston

Glover F, Klastorin T, Klingman D (1974) Optimal weighted ancestry relationships. Manage Sci 20:1190–1193

Goddard ST (1983) Tournament rankings. Manage Sci 29(12):1385–1392

Goemans MX, Hall LA (1996) The strongest facets of the acyclic subgraph polytope are unknown. In: Cunningham WH, McCormick ST, Queyranne M (eds). Integer programming and optimization, lecture notes in computer science 1084, Springer, Heidelberg, pp 415–429

Goldberg M (1966) Results on the automorphism group of a graph, M.Sc. Thesis, University of Alberta

Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading

González CG, Pérez-Brito D (2001) A variable neighborhood search for solving the linear ordering problem. In: Proceedings of MIC’2001–4th Metaheuristics International Conference, pp 181–185

Grindberg E, Dambit Y (1965) Some properties of graphs containing circuits. Latv math ezh 65–70 (in Russian)

Grötschel M, Jünger M, Reinelt G (1984a) A cutting plane algorithm for the linear ordering problem. Oper Res 32:1195–1220

Grötschel M, Jünger M, Reinelt G (1984b) Optimal triangulation of large real-world input-output-matrices. Statistische Hefte 25:261–295

Grötschel M, Jünger M, Reinelt G (1985a) On the acyclic subgraph polytope. Math Program 33:1–27

Grötschel M, Jünger M, Reinelt G (1985b) Facets of the linear ordering polytope. Math Program 33:43–60

Grötschel M, Jünger M, Reinelt G (1985c) Acyclic subdigraphs and linear orderings: polytopes, facets, and a cutting plane algorithm. In: Rival I (ed) Graphs and orders. D Reidel Publishing Company 217–264

Guénoche A (1977) Un algorithme pour pallier l’effet Condorcet. RAIRO 11(1):77–83

Guénoche A (1986) A. B. C. D. : logiciel d’analyses booléennes et combinatoires des données, notice d’utilisation. G. R. T. C, Marseille

Guénoche A (1988) Order at minimum distance of a valued tournament. Communication to Modélisation, Analyse et Agrégation des Préférences et des Choix (TRAP 3), Marseille-Luminy

Guénoche A, Vandeputte-Riboud B, Denis J-B (1994) Selecting varieties using a series of trials and a combinatorial ordering method. Agronomie 14:363–375

Guénoche A (1995) How to choose according to partial evaluations. In: Bouchon-Meunier B, et al. (eds) Advances in intelligent computing, IPMU’94. Lecture notes in computer sciences 945. Springer, Heidelberg, pp. 611–618

Guénoche A (1996) Vainqueurs de Kemeny et tournois difficiles. Math Inf Sci Hum 133:57–66

Guilbaud GT (1952) Les théories de l’intérêt général et le problème logique de l’agrégation. économie appliquée 5 (4), reprint in éléments de la théorie des jeux, Dunod, Paris, 1968

Guy RK (1967) A coarseness conjecture of Erdös. J Comb Theory 3:38–42

Hardouin Duparc J (1975) Quelques résultats sur l’ < < indice de transitivité > > de certains tournois. Mathématiques et Sciences humaines 51:35–41

Hassin R, Rubinstein S (1994) Approximations for the maximum acyclic subgraph problem. Inform Process Lett 51(3):133–140

Huang G, Lim A (2003) Designing a hybrid genetic algorithm for the linear ordering problem. In: Proceedings of “Genetic and Evolutionary Computation Conference (GECCO) 2003”, part I. Springer, Heidelberg LNCS 2723, pp 1053–1064

Huber L (1976) Seriation using asymmetric proximity measures. Br J Math Statist Psychol 29:32–52

Hubert L, Schulz J (1975) Maximum likehood paired-comparison ranking and quadratic assignment. Biometrika 62(3):655–659

Hudry O (1989) Recherche d’ordres médians : complexité, algorithmique et problèmes combinatoires. PhD thesis, ENST, Paris

Hudry O (1997a) Algorithms for the aggregation of ordinal preferences: a review. In: Proceedings of the first conference on operations and quantitative management (ICOQM), pp 169–176

Hudry O (1997b) Nombre maximum d’ordres de Slater des tournois T vérifiant σ(T) = 1. Mathématiques, Informatique et Sciences humaines 140:51–58

Hudry O (1998) Tournois et optimisation combinatoire. Habilitation à diriger des recherches, Université Paris 6, Paris, 1998

Hudry O (2004) A note on “Banks winners in tournaments are difficult to recognize” by G.J. Woeginger. Soc Choice Welfare 23:113–114

Hudry O (2006) On the difficulty of computing the winners of a tournament. Annales du LAMSADE 6, In: Proceedings of the workshop on voting theory and preference modelling, DIMACS, 2006, pp 181–191

Hudry O (2007) Complexity results on the aggregation of linear orders into median orders. Ann Oper Res (in press)

Hudry O (2007) Complexity of Slater problems (in preparation)

Isaak G (1995) Tournaments as feedback arc sets. Electron J Comb 2:R20

Isaak G, Tesman B (1991) The weighted reversing number of a digraph. Congressus Numerantium 83:115–124

Jacquet-Lagrèze É (1969) L’agrégation des opinions individuelles. Informatique et Sciences humaines 4:1–21

Jung H.A (1970) On subgraphs without cycles in a tournament. In: P. Erdös, A. Renyi, V.T. Sös (eds) Combinatorial theory and its applications II, North-Holland, Amsterdam, pp 675–677

Jünger M (1985) Polyhedral combinatorics and the acyclic subdigraph problem. Heldermann Verlag, Berlin

Kaas R (1981) A branch and bound algorithm for the acyclic subgraph problem. Eur J Oper Res 8:355–362

Kadane JB (1966) Some equivalence classes in paired comparisons. Ann Math Statist 37:488–494

Kano M, Sakamoto A (1985) Ranking the vertices of a paired comparison digraph. SIAM J Alg Disc Meth 6(1):79–92

Karp R (1972) Reducibility among combinatorial problems. In: Miller RE, Tatcher JW (eds). Complexity of computer computations. Plenum Press, New York, pp. 85–103

Kaykobad M, Ahmed QNU, Shafiqul Khalid ATM, Bakhtiar R-A (1995) A new algorithm for ranking players of a round-robin tournament. Comput Oper Res 22(2):221–226

Kemeny JG (1959) Mathematics without numbers. Daedalus 88:577–591

Kendall MG (1938) Rank correlation methods. Hafner, New York

Kendall MG, Babington Smith B (1940) On the method of paired comparisons. Biometrika 33: 239–251

Klamler C (2003) Kemeny’s rule and Slater’s rule: a binary comparison. Econ Bull 4(35):1–7

Klamler C (2004) The Dodgson ranking and its relation to Kemeny’s method and Slater’s rule. Soc Choice Welfare 23:91–102

Koppen M (1995) Random utility representation of binary choice probabilities: critical graphs yielding critical necessary conditions. J Math Psych 19:21–39

Korte B (1979) Approximation algorithms for discrete optimization problems. Ann Disc Math 4:85–120

Korte B, Oberhofer W (1968) Zwei Algorithmen zur Lösung eines komplexen Reihenfolgeproblems. Unternehmensforschung 12:217–231

Korte B, Oberhofer W (1969) Zur Triangulation von Input-Output-Matrizen. Jahrbuch Nationaloekon Statist 182:398–433

Kotzig, A (1975) On the maximal order of cyclicity of antisymmetric directed graphs. Disc Math 12:17–25

Laffond G, Laslier J-F (1991) Slater’s winners of a tournament may not be in the Banks set. Soc Choice Welfare 8:355–363

Laffond G, Laslier J-F, Le Breton M (1991a) Choosing from a tournament: a progress report and some new results. Technical report, CNAM, Paris

Laffond G, Laslier J-F, Le Breton M (1991b) A game-theoretical method for ranking the participants in a tournament”, Technical report, CNAM, Paris

Laffond G, Laslier J-F, Le Breton M (1993) The Bipartisan set of a tournament game. Games Econ Behav 5:182–201

Landau HG (1953) On dominance relations and the structure of animal societies III. The condition for a score structure. Bull Math Biophys 13:1–19

Laguna M, Marti R, Campos V (1999) Intensification and diversification with elite tabu search solutions for the linear ordering problem. Comput Oper Res 26(12):1217–1230

Laslier J-F (1997) Tournament solutions and majority voting. Springer, Heidelberg

Lawler EL (1964) A comment on minimum feedback arc sets. IEEE Trans Circuit Theory 11:296–297

Leighton T, Rao S (1988) An approximation max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: Proceedings of the 29th annual symposium on foundations of computer science, pp 422–431

Lemaréchal C (2003) The omnipresence of Lagrange, 4OR 1(1):7–25

Lempel A, Cederbaum I (1966) Minimum feedback arc and vertex sets of a directed graph. I E E E Trans Circuit Theory 13:399–403

Lenstra HW Jr (1973) The acyclic subgraph problem. Technical report BW26, Mathematisch Centrum, Amsterdam

Lenstra JK (1977) Sequencing by enumerative methods. Mathematical Centre Tracts 69, Mathematisch Centrum, Amsterdam

Leung J, Lee J (1994) More facets from fences for linear ordering and acyclic subgraph polytopes. Disc Appl Mathe 50:185–200

Loiseau I, Mendez-Dias I, Nasini G (1993) Determinacion del rango disyuntivo de facetas del problema de ordinacion lineal. Anales XXII JAIIO, pp 124–130

Marcotorchino J-F, Michaud P (1979) Optimisation en analyse ordinale de données, Masson, Paris

Matousek J, Nesetril J (1998) Invitation to Discrete Mathematics, Clarendon Press, Oxford University Press, New York

McGarvey D (1953) A theorem on the construction of voting paradoxes. Econometrica 21:608–610

McKey B (2006) http://cs.anu.edu.au/~bdm/data/digraphs.html

McLean I, Urken A (1995) Classics of social choice, University of Michigan Press

Méndez-Díaz I, Nasini G, Zabala P (submitted for publication) The disjunctive rank and cutting plane algorithms using of facets of the linear ordering polytope

Mendonça D, Raghavachari M (2000) Comparing the efficacy of ranking methods for multiple round-robin tournaments. Eur J Oper Res 123:593–605

Merchant DK, Rao MR (1976) Majority decisions and transitivity: some special cases. Manage Sci 23(2):125–130

Miller N (1980) A new solution set for tournaments and majority voting: Further graph-theoretical approaches to the theory of voting. Am J Polit Sci 24(1):68–96

Mitchell JE, Borchers B (1996) Solving real world linear ordering problems using a primal-dual interior point cutting plane method. Ann Oper Res 62:253–276

Mitchell JE, Borchers B (2000) Solving linear ordering problems with a combined interior point/ simplex cutting plane algorithm. In: Frenk HL, Roos K, Terlaky T, Zhang S (eds). High Performance Optimization. Kluwer Academic Publishers, Dordrecht, pp. 349–366

Mitchell J (2007) Generating linear ordering problems, http://www.rpi.edu/~mitchj/generators/ linord/

Monjardet B (1973) Tournois et ordres médians pour une opinion, Mathématiques et Sciences humaines 43:55–73

Monjardet B (1979) Relations à éloignement minimum de relations binaires, note bibliographique. Mathématiques et Sciences humaines 67:115–122

Monjardet B (1990) Sur diverses formes de la “règle de Condorcet” d’agrégation des préférences. Math Inf Sci hum 111:61–71

Monsuur H, Storcken T (1997) Measuring intransitivity. Math Soc Sci 34:125–152

Moon JW (1968) Topics on tournaments, Holt, Rinehart and Winston

Nalivaiko V (1997) The linear ordering polytope. Preprint 39/97, Faculty of Mathematics of the Otto-von-Guericke-University of Magdeburg

Nishihara O, Kumamoto H, Inoue K (1989) The new formulations of minimum feedback arc set problem. In: Brexinski C (ed) Numerical and applied mathematics. J.C. Baltzer AG, Scientific Publishing Co

Nutov Z, Penn M (1995) On the integral dicycle packings and covers and the linear ordering polytope. Disc Appl Math 60:293–309

Nutov Z, Penn M (1996) On non (0,1/2,1) Extreme Points of the Generalized Transitive Tournament Polytope. Linear Algebra and its applications 233:149–159

Orlin JB (1981) unpublished manuscript

Papadimitriou C, Yannakakis M (1991) Optimization, approximation, and complexity classes. J Comput Syst Sci 43:425–440

Phillips JPN (1967) A procedure for determining Slater’s i and all nearest adjoining orders. British Journal of Mathematical and Statistical Psychology 20:217–225

Phillips JPN (1969) A further procedure for determining Slater’s i and all nearest adjoining orders. Br J Math Stat Psychol 22:97101

Phillips JPN (1976) On an algorithm of Smith and Payne for determining Slater’s i and all nearest adjoining orders. Br J Math Stat Psychol 29:126–127

Poljak S, Turzík D (1986) A polynomial time heuristic for certain subgraph optimization problems with guaranteed lower bound. Disc Math 58:99–104

Poljak S, Rödl V, Spencer J (1988) Tournament ranking with expected profit in polynomial time. SIAM J Disc Math 1(3):372–376

Raman V, Saurabh S (2006) Parameterized algorithms for feedback set problems and their duals in tournaments. Theor Comput Sci 351:446–458

Rédei L (1934) Ein kombinatorischer Satz. Acta Litt Szeged 7:39–43

Reid KB (1969) On set of arcs containing no cycles in tournaments. Canad. Math Bull 12:261–264

Reid KB (1983) Monochromatic reachability, complementary cycles and single arc reversals in tournaments. In: Graph Theory, Proceedings of the First Southeast Asian Graph Theory Colloquium held in Singapore (May 1983). Springer, Lecture Notes in Mathematics 1073, Berlin, pp 11–21

Reid KB (2004) Tournaments. In: Gross JL, Yellen J (eds). Handbook of Graph Theory. CRC Press, Boca Raton, pp. 156–184

Reid KB, Beineke LW (1978) Tournaments. In: Beineke LW, Wilson RJ (eds). Selected topics in graph theory. Academic, New York, pp. 169–204

Reinelt G (1985) The linear ordering problem: algorithms and applications. Research and Exposition in Mathematics 8, Heldermann Verlag, Berlin

Reinelt G (1993) A Note on Small Linear-Ordering Polytopes. Disc Comput Geometry 10:67–78

Remage R, Thompson WA (1964) Rankings from paired comparison. Ann math Statist 35:739–747

Remage R, Thompson WA (1966) Maximum likelihood paired comparison rankings. Biometrika 53:143–149

Rubinstein A (1980) Ranking the participants in a tournament. SIAM J Appl Math 98:108–11

Ryser HJ (1964) Matrices of zeros and ones in combinatorial mathematics. In: Recent advances in matrix theory, University of Wisconsin Press, Madison, pp 103–124

Schiavinotto T, Stützle T (2003) Search space analysis of the linear ordering problem. In: Raidl GR et al. (eds). Applications of evolutionary computing. Lecture notes in computer science 2611. Springer, Berlin, pp. 322–333

Schiavinotto T, Stützle T (2004) The linear ordering problem: instances, search space analysis and algorithms. J Math Model Algorithms 3(4):367–402

Schrijver A (2003) Combinatorial optimization. Polyhedra and efficiency. Springer, Berlin

Schwartz T (1990) Cyclic tournaments and cooperative majority voting: a solution. Soc Choice Welfare 7:19–29

Seymour P (1995) Packing directed circuits fractionally. Combinatorica 15(2):281–288

Slater P (1961) Inconsistencies in a schedule of paired comparisons. Biometrika 48:303312

Smith WD (2007) http://rangevoting.org/PuzzDG.html

Smith AFM, Payne CD (1974) An algorithm for determining Slater’s i and all nearest adjoining orders. Br J Math Stat Psychol 27:4952

Spencer J (1971) Optimal ranking of tournaments. Networks 1:135–138

Spencer J (1978) Nonconstructive methods in discrete mathematics. In: Rota GC (eds). Studies in combinatorics. Mathematical Association of America, Washington DC, pp. 142–178

Spencer J (1987) Ten lectures on the probabilistic method. CBMS-NSF regional conference series in applied mathematics N° 52, SIAM, Philadelphy

Stearns R (1959) The voting problem. Am Math Monthly 66:761–763

Szele T (1943) Kombinatorikai vizsgálatok az irányított teljes gráffal kapesolatban. Mat Fiz Lapok 50:223–256, German translation: Untersuchungen über gerichtete vollständige Graphen. Publ Math Debrecen 13(1966):145–168

Thomassen C (1975) Transversals of circuits in the lexicographic product of directed graphs. Mathématiques et Sciences Humaines 51:43–45

Thomassen C (1987) Counterexamples to Adám’s conjecture on arc reversals in directed graphs. J Comb Theory 42, series B:128–130

Tucker AW (1960) On directed graphs and integer programs. In: 1960 symposium on combinatorial problems, Princeton University, Princeton

Tüshaus U (1983) Aggregation binärer Relationen in der qualitativen Datenanalyse. Mathematical Systems in Economics 82, Verlagsgruppe Athenäum/Hain/Hanstein

van Zuylen A (2005) Deterministic approximation algorithms for ranking and clusterings. Cornell ORIE Tech. Report No. 1431

Vazirani VV (2003) Approximation algorithms. Springer, Berlin

Wakabayashi Y (1986) Aggregation of binary relations: algorithmic and polyhedral investigations, PhD thesis, Augsburg university

Wakabayashi Y (1998) The Complexity of Computing Medians of Relations. Resenhas 3(3):323–349

Wei T (1952) The Algebraic Foundations of ranking Theory. Ph D thesis, Cambridge University, Cambridge

Wessels H (1981) Triangulation und Blocktriangulation von Input-Output Tabellen. Deutsches Institut für Wirtschaftsforschung: Beiträge zur Strukturforshung, Heft 63, Berlin

Woeginger GJ (2003) Banks winners in tournaments are difficult to recognize. Soc Choice Welfare 20(3):523–528

Woirgard F (1997) Recherche et dénombrement des ordres médians des tournois. PhD thesis, ENST, Paris

Young HP (1978) On permutations and permutation polytopes. Math Program Study 8:128–140

Young HP (1988) Condorcet Theory of Voting. Am Polit Sci Rev 82:1231–1244

Younger DH (1963) Minimum feedback arc sets for a directed graph. IEEE Trans Profes Tech Group Circuit Theory 10(2):238–245

Zermelo E (1929) Die Berechnung der Turnier-Ergebnisse als ein maximal Problem der Warscheinlichkeistsrechnung. Math Zeitung 29:436–460