A survey on the linear ordering problem for weighted or unweighted tournaments. (English) Zbl 1126.05052
A relation \(R\) defined on a finite set \(X\) of \(n\) elements (that may represent different teams or alternatives, for example) is a preference relation if for each pair of distinct elements \(u\) and \(v\) either \(uRv\) or \(vRu\), but not both. Let there be given a collection \(P\) of \(m\) preference relations on the same set \(X\). The general linear ordering problem is to determine a single linear order \(O\) with the property that the total number of disagreements between \(O\) and the preferences in \(P\) is minimized. (There may or may not be weights associated with the preferences to be taken into account.) The authors survey work done on various formulations of this and related problems, both when \(m=1\) and in general. In particular, they present complexity results and bounds and discuss various algorithms that have been developed for treating these problems.
Reviewer: J. W. Moon (Edmonton)
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C38 | Paths and cycles |
| 05C90 | Applications of graph theory |
| 06A05 | Total orders |
| 06A07 | Combinatorics of partially ordered sets |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 90C10 | Integer programming |
| 90C27 | Combinatorial optimization |
| 90C35 | Programming involving graphs or networks |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
aggregation of preferences; voting theory; social choice; linear ordering problem; Kemeny’s problem; Slater’s problem; median order; reversing set; feedback arc set; acyclic subgraph; optimal triangulation; graph theory; tournament solutions; complexity; combinatorial optimization; combinatoricsReferences:
| [1] | Adám A (1964) Problem. In: Theory of graphs and its applications. Proc Coll Smolenice, Czech Acad Sci Publ |
| [2] | Adler I, Alon N, Ross SM (2001) On the number of Hamiltonian paths in tournaments. Random Struct Alg 18:291–296 · Zbl 0982.05056 · doi:10.1002/rsa.1010 |
| [3] | Ailon N, Alon N (2007) Hardness of fully dense problems (submitted) · Zbl 1121.68054 |
| [4] | 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 · Zbl 1192.90252 |
| [5] | Ali I, Cook WD, Kress M (1986) On the minimum violations ranking of a tournament. Manage Sci 32:660–674 · Zbl 0601.90003 · doi:10.1287/mnsc.32.6.660 |
| [6] | Alon N (1990) The maximum number of Hamiltonian paths in tournaments. Combinatorica 10: 319–324 · Zbl 0724.05036 |
| [7] | Alon N (2006) Ranking tournaments. SIAM J Discrete Mathe 20(1):137–142 · Zbl 1112.05043 · doi:10.1137/050623905 |
| [8] | Alon N, Spencer J (2000) The probabilistic method, 2nd edn. Wiley, New York · Zbl 0996.05001 |
| [9] | Alspach B (1967) Cycles of each length in regular tournaments. Can Math Bull 10:283–286 · Zbl 0148.43602 · doi:10.4153/CMB-1967-028-6 |
| [10] | Alspach B (1968) A combinatorial proof of a conjecture of Goldberg and Moon. Can Math Bull 11:655–661 · Zbl 0177.26902 · doi:10.4153/CMB-1968-078-3 |
| [11] | 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 · Zbl 0565.90030 |
| [12] | 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 · Zbl 1154.90602 |
| [13] | Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (2003) Complexity and approximation, 2nd edn. Springer, Berlin · Zbl 0937.68002 |
| [14] | 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 |
| [15] | Banks J (1985) Sophisticated voting outcomes and agenda control. Soc Choice Welfare 2:295–306 · Zbl 0597.90011 · doi:10.1007/BF00649265 |
| [16] | Banks J, Bordes G, Le Breton M (1991) Covering relations, closest orderings and hamiltonian bypaths in tournaments. Soc Choice Welfare 8:355–363 · Zbl 0734.90027 · doi:10.1007/BF00183046 |
| [17] | Barbut M (1966) Note sur les ordres totaux à distance minimum d’une relation binaire donnée. Mathématiques et Sciences humaines 17:47–48 |
| [18] | Bar-Noy A, Naor J (1990) Sorting, minimal feedback sets, and Hamilton paths in tournaments. SIAM J Disc Math 3(1):7–20 · Zbl 0686.68052 · doi:10.1137/0403002 |
| [19] | Barthélemy J-P, Monjardet B (1981) The median procedure in cluster analysis and social choice theory. Math Soc Sci 1:235–267 · Zbl 0486.62057 · doi:10.1016/0165-4896(81)90041-X |
| [20] | 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 |
| [21] | Barthélemy J-P, Guénoche A, Hudry O (1989) Median linear orders: heuristics and a branch and bound algorithm. EJOR 41:313–325 · Zbl 0689.90003 · doi:10.1016/0377-2217(89)90442-6 |
| [22] | 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 · Zbl 0826.05032 · doi:10.1016/0166-218X(94)00042-C |
| [23] | Barthélemy J-P, Cohen G, Lobstein A (1996) Algorithmic Complexity and Communication Problems. UCL Press, London |
| [24] | 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 · Zbl 0672.90004 · doi:10.1007/BF00303169 |
| [25] | Becker O (1967) Das Helmstädtersche Reihenfolgeproblem–die Effizienz verschiedener Näherungsverfahren. In: Computers uses in the Social Science. Vienna |
| [26] | 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 |
| [27] | Berge C (1985) Graphs. North-Holland, Amsterdam |
| [28] | 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 · Zbl 0800.68607 |
| [29] | Berger B, Shor PW (1997) Tight bounds for the maximum acyclic subgraph problem. J Algor 25:1–18 · Zbl 0888.68088 · doi:10.1006/jagm.1997.0864 |
| [30] | Bermond J-C (1972) Ordres à distance minimum d’un tournoi et graphes partiels sans circuits maximaux. Math Sci hum 37:5–25 · Zbl 0239.05122 |
| [31] | 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 · Zbl 0302.05110 |
| [32] | Bermond J-C, Kodratoff Y (1976) Une heuristique pour le calcul de l’indice de transitivité d’un tournoi. RAIRO 10(3):83–92 |
| [33] | Bertacco L, Brunetta L, Fischetti M (2004) The linear ordering problem with cumulative costs. Technical report, University of Padova, and EJOR (in press) · Zbl 1146.90497 |
| [34] | Black D (1958) The theory of committees and elections. Cambridge University Press, London · Zbl 0091.15706 |
| [35] | Blin JM, Whinston AB (1974) A note on majority rule under transitivity constraints. Manage Sci 20:1439–1440 · Zbl 0363.90006 · doi:10.1287/mnsc.20.11.1439 |
| [36] | Blin JM, Whinston AB (1975) Discriminant functions and majority voting. Manage Sci 21: 1029–1041 · Zbl 0318.62043 · doi:10.1287/mnsc.21.5.557 |
| [37] | Boenchendorf K (1982) Reihenfolgenprobleme/Mean-flow-time sequencing. Mathematical Systems in Economics 74, Verlagsgruppe Athanäum/Hain/Scriptor/Hanstein · Zbl 0535.90030 |
| [38] | Bolotashvili G, Kovalev M, Girlich E (1999) New Facets of the Linear Ordering Polytope. SIAM J Discrete Math 12(3):326–336 · Zbl 0966.90085 · doi:10.1137/S0895480196300145 |
| [39] | Borda J-C (chevalier de) (1784) Mémoire sur les élections au scrutin, Histoire de l’Académie Royale des Sciences pour 1781, Paris |
| [40] | Bowman VJ, Colantoni CS (1973) Majority rule under transitivity constraints. Manage Sci 19: 1029–1041 · Zbl 0285.90003 · doi:10.1287/mnsc.19.9.1029 |
| [41] | Brualdi RA, Qiao L (1983) Upsets in round robin tournaments. J Combin Theory 35 Ser B:62–77 · Zbl 0519.05033 |
| [42] | 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 · Zbl 0553.05039 |
| [43] | Burkov VN, Groppen VO (1972) Branch cuts in strongly connected graphs and permutation potentials. Auto Remote Control 6:111–119 · Zbl 0252.90055 |
| [44] | 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 |
| [45] | 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 · Zbl 1175.90424 · doi:10.1023/A:1012793906010 |
| [46] | Chanas S, Kobylanski P (1996) A new heuristic algorithm solving the linear ordering problem. Comput Optim Appl 6:191–205 · Zbl 0860.90100 |
| [47] | Chaovalitwongse W, Pardalos PM (1997) GRASP with Path-Relinking for the Linear Ordering Problem. Industrial and Systems Engineering Working Paper, Rutgers University |
| [48] | 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 · Zbl 1120.05038 · doi:10.1017/S0963548306007887 |
| [49] | 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 · Zbl 0846.05040 |
| [50] | 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 · Zbl 0845.05050 |
| [51] | 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 · Zbl 0974.05502 · doi:10.1016/0377-2217(95)00294-4 |
| [52] | 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 · Zbl 0897.90003 |
| [53] | 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 · Zbl 0870.90095 |
| [54] | Charon I, Guénoche A, Hudry O, Woirgard F (1997a) New results on the computation of median orders. Disc Math 165–166:139–154 · Zbl 0878.68090 |
| [55] | 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 · Zbl 0895.05027 · doi:10.1016/S0166-218X(97)88689-1 |
| [56] | Charon I, Hudry O (1998) Lamarckian genetic algorithms applied to the aggregation of preferences. Ann Oper Res 80:281–297 · Zbl 0907.90009 · doi:10.1023/A:1018976217274 |
| [57] | Charon I, Hudry O (2000) Slater orders and Hamiltonian paths of tournaments. Electron Notes Disc Math 5:60–63 · Zbl 1412.05124 · doi:10.1016/S1571-0653(05)80125-8 |
| [58] | Charon I, Hudry O (2001a) The noising methods: a generalization of some metaheuristics. Eur J Oper Res 135(1):86–101 · Zbl 1063.90042 · doi:10.1016/S0377-2217(00)00305-2 |
| [59] | 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) |
| [60] | 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 · Zbl 1005.90051 |
| [61] | Charon I, Hudry O (2003) Links between the Slater index and the Ryser index of tournaments. Graphs Combina 19(3):309–322 · Zbl 1023.05065 · doi:10.1007/s00373-002-0510-z |
| [62] | 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 · Zbl 1111.90121 · doi:10.1016/j.dam.2005.04.020 |
| [63] | Charon I, Hudry O (2007) Building a mi nimum profile or tournaments or of linear orders from a weighted graph (in preparation) |
| [64] | Chartrand G, Geller D, Hedetniemi S (1971) Graphs with forbidden subgraphs. J Comb Theory 10 (1) series B:12–41 · Zbl 0223.05101 |
| [65] | Christof T, Reinelt G (1996) Combinatorial optimization and small polytopes. Top 4(1):1–64 · Zbl 0858.90107 · doi:10.1007/BF02568602 |
| [66] | Christof T, Reinelt G (1997a) Low-dimensional Linear Ordering Polytopes. Working paper, University of Heidelberg |
| [67] | Christof T, Reinelt G (1997b) Small instances relaxations for solving linear ordering problems by branch-and-cut. Technical report, University of Heidelberg |
| [68] | Christof T, Reinelt G (2001) Algorithmic aspects of using small instance relaxations in parallel branch-and-cut. Algorithmica 30(4):597–629 · Zbl 0973.90064 · doi:10.1007/s00453-001-0029-3 |
| [69] | Christophe J, Doignon J-P, Fiorini S (2004) The biorder. Order 21/1:61–82 · Zbl 1072.52009 · doi:10.1007/s11083-004-5129-7 |
| [70] | Cohen W, Schapire R, Singer Y (1999) Learning to order things. J Artif Intell Res 10:213–270 · Zbl 0915.68031 |
| [71] | Condorcet MJAN, Caritat (marquis de) (1785) Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix, Paris |
| [72] | Congram RK (2000) Polynomially searchable exponential neighbourhoods for sequencing problems in combinatorial optimisation. PhD thesis, University of Southampton |
| [73] | Conitzer V (2005) Computing Slater Rankings Using Similarities Among Candidates. IBM research report RC23748 (W0510–105) |
| [74] | 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 |
| [75] | Cook WD, Golan I, Kress M (1988) Heuristics for ranking players in a round robin tournament. Comput Oper Res 15(2):135–144 · doi:10.1016/0305-0548(88)90006-8 |
| [76] | Cook WD, Doyle J, Green R, Kress M (1996) Ranking players in multiple tournaments. Comput Oper Res 23(9):869–880 · Zbl 0859.90004 · doi:10.1016/0305-0548(95)00082-8 |
| [77] | Copeland AH (1951) A ”reasonable” social welfare function. Seminar on applications of mathematics to social sciences, University of Michigan |
| [78] | Coppersmith D, Winograd S (1990) Matrix multiplication via arithmetic progressions. J Symbolic Comput 9:251–280 · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2 |
| [79] | 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 · Zbl 1192.05060 |
| [80] | Czygrinow A, Poljak S, Rödl V (1999) Constructive quasi-Ramsey numbers and tournament ranking. SIAM J Disc Math 12(1):48–63 · Zbl 0933.68099 · doi:10.1137/S0895480197318301 |
| [81] | 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 |
| [82] | 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 |
| [83] | Debord B (1987b) Axiomatisation de procédures d’agrégation de préférences. PhDthesis, Université scientifique technologique et médicale de Grenoble |
| [84] | de Cani JS (1969) Maximum likelihood paired comparison ranking by linear programming. Biometrika 3:537–545 · Zbl 0188.50101 |
| [85] | de Cani JS (1972) A branch and bound algorithm for maximum likelihood paired comparison ranking. Biometrika 59:131–135 · Zbl 0245.62037 · doi:10.1093/biomet/59.1.131 |
| [86] | 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 · Zbl 0531.05036 |
| [87] | Dixon JD (1967) The maximum order of the group of a tournament. Can Math Bull 10:503–505 · Zbl 0203.01501 · doi:10.4153/CMB-1967-048-9 |
| [88] | 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 |
| [89] | 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 · Zbl 1096.05050 · doi:10.1016/j.jmp.2006.01.001 |
| [90] | 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 · Zbl 1183.68419 |
| [91] | Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin |
| [92] | Dréo J, Petrowski A, Taillard E, Siarry P (2006) Metaheuristics for hard Optimization, Methods and Case Studies. Springer, Berlin · Zbl 1118.90058 |
| [93] | Duarte A, Laguna M, Marti R (2006) Tabu search for the linear ordering problem with cumulative costs, Technical Report, University of Valencia |
| [94] | 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 |
| [95] | Dutta B (1988) Covering sets and a new Condorcet choice correspondence. J Econ Theory 44(1988):63–80 · Zbl 0652.90013 · doi:10.1016/0022-0531(88)90096-8 |
| [96] | 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 |
| [97] | Eades P, Lin X (1995) A new heuristic for the feedback arc set problem. Aust J Comb 12:15–26 · Zbl 0838.68086 |
| [98] | 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 · Zbl 0787.68078 · doi:10.1016/0020-0190(93)90079-O |
| [99] | 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 · Zbl 0136.44901 |
| [100] | Erdös P, Moon JW (1965) On sets of consistent arcs in a tournament. Canad Math Bull 8:269–271 · Zbl 0137.43301 · doi:10.4153/CMB-1965-017-1 |
| [101] | Even G, Naor JS, Sudan M, Schieber B (1998) Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20(2):151–174 · Zbl 0897.68078 · doi:10.1007/PL00009191 |
| [102] | Fagin R, Kumar R, Mahdian M, Sivakumar D, Vee E (2005) Rank aggregation: an algorithmic perspective. Unpublished Manuscript · Zbl 1414.91126 |
| [103] | Festa P, Pardalos P, Resende M (1999) Feedback set problems. In: handbook of combinatorial optimization 4, Kluwer Academic Publishers, Boston · Zbl 1253.90193 |
| [104] | Fiorini S (2001a) Polyhedral combinatorics of order polytopes. PhD thesis, Université libre de Bruxelles · Zbl 1006.20002 |
| [105] | Fiorini S (2001b) Determining the automorphism group of the linear ordering polytope. Disc Appl Math 112/1–3:121–128 · Zbl 1006.20002 · doi:10.1016/S0166-218X(00)00312-7 |
| [106] | Fiorini S, Fishburn P (2003) Facets of linear signed order polytopes. Disc Appl Math 131/3:597–610 · Zbl 1077.91017 · doi:10.1016/S0166-218X(03)00224-5 |
| [107] | Fiorini S (2006a) How to recycle your facets. Disc Optim 3/2:136–153 · Zbl 1146.90478 · doi:10.1016/j.disopt.2005.10.007 |
| [108] | Fiorini S (2006b) 0, 1/2-cuts and the linear ordering problem: surfaces that define facets. SIAM J Disc Math 20/4: 893–912 · Zbl 1126.05081 · doi:10.1137/S0895480104440985 |
| [109] | Fishburn P (1977) Condorcet social choice functions. SIAM J Appl Math 33:469–489 · Zbl 0369.90002 · doi:10.1137/0133030 |
| [110] | Fishburn P (1992) Induced binary probabilities and the linear ordering polytope: a status report. Math Soc Sci 23:67–80 · Zbl 0751.90004 · doi:10.1016/0165-4896(92)90038-7 |
| [111] | 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 · Zbl 0691.90088 · doi:10.1002/net.3230200102 |
| [112] | Flueck JA, Korsh JF (1974) A branch search algorithm for maximum likelihood paired comparison ranking. Biometrika 61(3):621–626 · Zbl 0295.62078 · doi:10.1093/biomet/61.3.621 |
| [113] | Fulkerson DR (1965) Upsets in round robin tournaments. Can J Math 17:957–969 · Zbl 0135.01304 · doi:10.4153/CJM-1965-091-7 |
| [114] | 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 · Zbl 1079.90110 |
| [115] | Garcia CG, Perez-Brito D, Campos V, Marti R (2006) Variable neighborhood search for the linear ordering problem. Comput Oper Res 33(12):35493565 · Zbl 1094.90039 · doi:10.1016/j.cor.2005.03.032 |
| [116] | Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. Freeman, New York · Zbl 0411.68039 |
| [117] | 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 |
| [118] | Glover F, Kochenberger GA (2003) Handbook of Metaheuristics. Kluwer Academic Publishers, Boston · Zbl 1058.90002 |
| [119] | Glover F, Klastorin T, Klingman D (1974) Optimal weighted ancestry relationships. Manage Sci 20:1190–1193 · Zbl 0303.90055 · doi:10.1287/mnsc.20.8.1190 |
| [120] | Goddard ST (1983) Tournament rankings. Manage Sci 29(12):1385–1392 · Zbl 0527.90047 · doi:10.1287/mnsc.29.12.1384 |
| [121] | 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 |
| [122] | Goldberg M (1966) Results on the automorphism group of a graph, M.Sc. Thesis, University of Alberta |
| [123] | Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading · Zbl 0721.68056 |
| [124] | 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 |
| [125] | Grindberg E, Dambit Y (1965) Some properties of graphs containing circuits. Latv math ezh 65–70 (in Russian) |
| [126] | Grötschel M, Jünger M, Reinelt G (1984a) A cutting plane algorithm for the linear ordering problem. Oper Res 32:1195–1220 · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195 |
| [127] | Grötschel M, Jünger M, Reinelt G (1984b) Optimal triangulation of large real-world input-output-matrices. Statistische Hefte 25:261–295 · doi:10.1007/BF02932410 |
| [128] | Grötschel M, Jünger M, Reinelt G (1985a) On the acyclic subgraph polytope. Math Program 33:1–27 · Zbl 0577.05034 |
| [129] | Grötschel M, Jünger M, Reinelt G (1985b) Facets of the linear ordering polytope. Math Program 33:43–60 · Zbl 0577.05035 · doi:10.1007/BF01582010 |
| [130] | 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 |
| [131] | Guénoche A (1977) Un algorithme pour pallier l’effet Condorcet. RAIRO 11(1):77–83 · Zbl 0356.90068 |
| [132] | 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 |
| [133] | 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 |
| [134] | 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 · doi:10.1051/agro:19940602 |
| [135] | 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 |
| [136] | Guénoche A (1996) Vainqueurs de Kemeny et tournois difficiles. Math Inf Sci Hum 133:57–66 · Zbl 0870.90096 |
| [137] | 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 |
| [138] | Guy RK (1967) A coarseness conjecture of Erdös. J Comb Theory 3:38–42 · Zbl 0149.41501 · doi:10.1016/S0021-9800(67)80014-0 |
| [139] | Hardouin Duparc J (1975) Quelques résultats sur l’ < < indice de transitivité > > de certains tournois. Mathématiques et Sciences humaines 51:35–41 |
| [140] | Hassin R, Rubinstein S (1994) Approximations for the maximum acyclic subgraph problem. Inform Process Lett 51(3):133–140 · Zbl 0942.68644 · doi:10.1016/0020-0190(94)00086-7 |
| [141] | 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 · Zbl 1028.68780 |
| [142] | Huber L (1976) Seriation using asymmetric proximity measures. Br J Math Statist Psychol 29:32–52 · Zbl 0334.92040 |
| [143] | Hubert L, Schulz J (1975) Maximum likehood paired-comparison ranking and quadratic assignment. Biometrika 62(3):655–659 · Zbl 0321.62080 · doi:10.1093/biomet/62.3.655 |
| [144] | Hudry O (1989) Recherche d’ordres médians : complexité, algorithmique et problèmes combinatoires. PhD thesis, ENST, Paris |
| [145] | 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 |
| [146] | Hudry O (1997b) Nombre maximum d’ordres de Slater des tournois T vérifiant {\(\sigma\)}(T) = 1. Mathématiques, Informatique et Sciences humaines 140:51–58 · Zbl 0940.05036 |
| [147] | Hudry O (1998) Tournois et optimisation combinatoire. Habilitation à diriger des recherches, Université Paris 6, Paris, 1998 |
| [148] | Hudry O (2004) A note on ”Banks winners in tournaments are difficult to recognize” by G.J. Woeginger. Soc Choice Welfare 23:113–114 · Zbl 1088.91506 · doi:10.1007/s00355-003-0241-y |
| [149] | 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 |
| [150] | Hudry O (2007) Complexity results on the aggregation of linear orders into median orders. Ann Oper Res (in press) |
| [151] | Hudry O (2007) Complexity of Slater problems (in preparation) |
| [152] | Isaak G (1995) Tournaments as feedback arc sets. Electron J Comb 2:R20 · Zbl 0829.68100 |
| [153] | Isaak G, Tesman B (1991) The weighted reversing number of a digraph. Congressus Numerantium 83:115–124 · Zbl 0768.05046 |
| [154] | Jacquet-Lagrèze É (1969) L’agrégation des opinions individuelles. Informatique et Sciences humaines 4:1–21 |
| [155] | 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 · Zbl 0207.23002 |
| [156] | Jünger M (1985) Polyhedral combinatorics and the acyclic subdigraph problem. Heldermann Verlag, Berlin · Zbl 0557.68045 |
| [157] | Kaas R (1981) A branch and bound algorithm for the acyclic subgraph problem. Eur J Oper Res 8:355–362 · Zbl 0465.90090 · doi:10.1016/0377-2217(81)90005-9 |
| [158] | Kadane JB (1966) Some equivalence classes in paired comparisons. Ann Math Statist 37:488–494 · Zbl 0171.40101 · doi:10.1214/aoms/1177699532 |
| [159] | Kano M, Sakamoto A (1985) Ranking the vertices of a paired comparison digraph. SIAM J Alg Disc Meth 6(1):79–92 · Zbl 0572.05030 · doi:10.1137/0606009 |
| [160] | Karp R (1972) Reducibility among combinatorial problems. In: Miller RE, Tatcher JW (eds). Complexity of computer computations. Plenum Press, New York, pp. 85–103 |
| [161] | 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 · Zbl 0814.90147 · doi:10.1016/0305-0548(94)E0024-2 |
| [162] | Kemeny JG (1959) Mathematics without numbers. Daedalus 88:577–591 |
| [163] | Kendall MG (1938) Rank correlation methods. Hafner, New York |
| [164] | Kendall MG, Babington Smith B (1940) On the method of paired comparisons. Biometrika 33: 239–251 · Zbl 0063.03216 · doi:10.1093/biomet/33.3.239 |
| [165] | Klamler C (2003) Kemeny’s rule and Slater’s rule: a binary comparison. Econ Bull 4(35):1–7 |
| [166] | Klamler C (2004) The Dodgson ranking and its relation to Kemeny’s method and Slater’s rule. Soc Choice Welfare 23:91–102 · Zbl 1088.91023 · doi:10.1007/s00355-003-0238-6 |
| [167] | Koppen M (1995) Random utility representation of binary choice probabilities: critical graphs yielding critical necessary conditions. J Math Psych 19:21–39 · Zbl 0897.92045 · doi:10.1006/jmps.1995.1003 |
| [168] | Korte B (1979) Approximation algorithms for discrete optimization problems. Ann Disc Math 4:85–120 · Zbl 0411.90052 · doi:10.1016/S0167-5060(08)70820-3 |
| [169] | Korte B, Oberhofer W (1968) Zwei Algorithmen zur Lösung eines komplexen Reihenfolgeproblems. Unternehmensforschung 12:217–231 · Zbl 0167.18403 · doi:10.1007/BF01918332 |
| [170] | Korte B, Oberhofer W (1969) Zur Triangulation von Input-Output-Matrizen. Jahrbuch Nationaloekon Statist 182:398–433 |
| [171] | Kotzig, A (1975) On the maximal order of cyclicity of antisymmetric directed graphs. Disc Math 12:17–25 · Zbl 0299.05107 · doi:10.1016/0012-365X(75)90092-8 |
| [172] | 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 · Zbl 0733.90008 · doi:10.1007/BF00183047 |
| [173] | Laffond G, Laslier J-F, Le Breton M (1991a) Choosing from a tournament: a progress report and some new results. Technical report, CNAM, Paris |
| [174] | Laffond G, Laslier J-F, Le Breton M (1991b) A game-theoretical method for ranking the participants in a tournament”, Technical report, CNAM, Paris |
| [175] | Laffond G, Laslier J-F, Le Breton M (1993) The Bipartisan set of a tournament game. Games Econ Behav 5:182–201 · Zbl 0770.90080 · doi:10.1006/game.1993.1010 |
| [176] | 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 |
| [177] | 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 · Zbl 1016.90081 · doi:10.1016/S0305-0548(98)00104-X |
| [178] | Laslier J-F (1997) Tournament solutions and majority voting. Springer, Heidelberg · Zbl 0948.91504 |
| [179] | Lawler EL (1964) A comment on minimum feedback arc sets. IEEE Trans Circuit Theory 11:296–297 |
| [180] | 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 |
| [181] | Lemaréchal C (2003) The omnipresence of Lagrange, 4OR 1(1):7–25 · Zbl 1046.90064 |
| [182] | 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 · Zbl 0191.55303 |
| [183] | Lenstra HW Jr (1973) The acyclic subgraph problem. Technical report BW26, Mathematisch Centrum, Amsterdam |
| [184] | Lenstra JK (1977) Sequencing by enumerative methods. Mathematical Centre Tracts 69, Mathematisch Centrum, Amsterdam · Zbl 0407.90025 |
| [185] | Leung J, Lee J (1994) More facets from fences for linear ordering and acyclic subgraph polytopes. Disc Appl Mathe 50:185–200 · Zbl 0817.52017 · doi:10.1016/0166-218X(92)00151-B |
| [186] | 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 |
| [187] | Marcotorchino J-F, Michaud P (1979) Optimisation en analyse ordinale de données, Masson, Paris |
| [188] | Matousek J, Nesetril J (1998) Invitation to Discrete Mathematics, Clarendon Press, Oxford University Press, New York |
| [189] | McGarvey D (1953) A theorem on the construction of voting paradoxes. Econometrica 21:608–610 · doi:10.2307/1907926 |
| [190] | McKey B (2006) http://cs.anu.edu.au/\(\sim\)bdm/data/digraphs.html |
| [191] | McLean I, Urken A (1995) Classics of social choice, University of Michigan Press |
| [192] | 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 |
| [193] | Mendonça D, Raghavachari M (2000) Comparing the efficacy of ranking methods for multiple round-robin tournaments. Eur J Oper Res 123:593–605 · Zbl 1068.91507 · doi:10.1016/S0377-2217(99)00110-1 |
| [194] | Merchant DK, Rao MR (1976) Majority decisions and transitivity: some special cases. Manage Sci 23(2):125–130 · Zbl 0349.90002 · doi:10.1287/mnsc.23.2.125 |
| [195] | 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 · doi:10.2307/2110925 |
| [196] | 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 · Zbl 0848.90086 · doi:10.1007/BF02206819 |
| [197] | 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 · Zbl 0965.90057 |
| [198] | Mitchell J (2007) Generating linear ordering problems, http://www.rpi.edu/\(\sim\)mitchj/generators/ linord/ |
| [199] | Monjardet B (1973) Tournois et ordres médians pour une opinion, Mathématiques et Sciences humaines 43:55–73 |
| [200] | Monjardet B (1979) Relations à éloignement minimum de relations binaires, note bibliographique. Mathématiques et Sciences humaines 67:115–122 · Zbl 0413.62045 |
| [201] | 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 |
| [202] | Monsuur H, Storcken T (1997) Measuring intransitivity. Math Soc Sci 34:125–152 · Zbl 0916.90006 · doi:10.1016/S0165-4896(97)00010-3 |
| [203] | Moon JW (1968) Topics on tournaments, Holt, Rinehart and Winston · Zbl 0191.22701 |
| [204] | Nalivaiko V (1997) The linear ordering polytope. Preprint 39/97, Faculty of Mathematics of the Otto-von-Guericke-University of Magdeburg |
| [205] | 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 |
| [206] | Nutov Z, Penn M (1995) On the integral dicycle packings and covers and the linear ordering polytope. Disc Appl Math 60:293–309 · Zbl 0826.05047 · doi:10.1016/0166-218X(94)00060-Q |
| [207] | 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 · Zbl 0842.05038 · doi:10.1016/0024-3795(94)00063-8 |
| [208] | Orlin JB (1981) unpublished manuscript |
| [209] | Papadimitriou C, Yannakakis M (1991) Optimization, approximation, and complexity classes. J Comput Syst Sci 43:425–440 · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X |
| [210] | 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 |
| [211] | Phillips JPN (1969) A further procedure for determining Slater’s i and all nearest adjoining orders. Br J Math Stat Psychol 22:97101 |
| [212] | 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 |
| [213] | Poljak S, Turzík D (1986) A polynomial time heuristic for certain subgraph optimization problems with guaranteed lower bound. Disc Math 58:99–104 · Zbl 0585.05032 · doi:10.1016/0012-365X(86)90192-5 |
| [214] | Poljak S, Rödl V, Spencer J (1988) Tournament ranking with expected profit in polynomial time. SIAM J Disc Math 1(3):372–376 · Zbl 0667.05030 · doi:10.1137/0401037 |
| [215] | Raman V, Saurabh S (2006) Parameterized algorithms for feedback set problems and their duals in tournaments. Theor Comput Sci 351:446–458 · Zbl 1086.68105 · doi:10.1016/j.tcs.2005.10.010 |
| [216] | Rédei L (1934) Ein kombinatorischer Satz. Acta Litt Szeged 7:39–43 · Zbl 0009.14606 |
| [217] | Reid KB (1969) On set of arcs containing no cycles in tournaments. Canad. Math Bull 12:261–264 · Zbl 0181.51901 · doi:10.4153/CMB-1969-032-x |
| [218] | 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 |
| [219] | Reid KB (2004) Tournaments. In: Gross JL, Yellen J (eds). Handbook of Graph Theory. CRC Press, Boca Raton, pp. 156–184 |
| [220] | Reid KB, Beineke LW (1978) Tournaments. In: Beineke LW, Wilson RJ (eds). Selected topics in graph theory. Academic, New York, pp. 169–204 |
| [221] | Reinelt G (1985) The linear ordering problem: algorithms and applications. Research and Exposition in Mathematics 8, Heldermann Verlag, Berlin · Zbl 0565.68058 |
| [222] | Reinelt G (1993) A Note on Small Linear-Ordering Polytopes. Disc Comput Geometry 10:67–78 · Zbl 0784.90063 · doi:10.1007/BF02573963 |
| [223] | Remage R, Thompson WA (1964) Rankings from paired comparison. Ann math Statist 35:739–747 · Zbl 0138.13206 · doi:10.1214/aoms/1177703572 |
| [224] | Remage R, Thompson WA (1966) Maximum likelihood paired comparison rankings. Biometrika 53:143–149 · Zbl 0138.13207 |
| [225] | Rubinstein A (1980) Ranking the participants in a tournament. SIAM J Appl Math 98:108–11 · Zbl 0442.05028 · doi:10.1137/0138009 |
| [226] | 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 |
| [227] | 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 · Zbl 1033.90512 |
| [228] | Schiavinotto T, Stützle T (2004) The linear ordering problem: instances, search space analysis and algorithms. J Math Model Algorithms 3(4):367–402 · Zbl 1079.90117 · doi:10.1023/B:JMMA.0000049426.06305.d8 |
| [229] | Schrijver A (2003) Combinatorial optimization. Polyhedra and efficiency. Springer, Berlin · Zbl 1041.90001 |
| [230] | Schwartz T (1990) Cyclic tournaments and cooperative majority voting: a solution. Soc Choice Welfare 7:19–29 · Zbl 0698.90008 · doi:10.1007/BF01832917 |
| [231] | Seymour P (1995) Packing directed circuits fractionally. Combinatorica 15(2):281–288 · Zbl 0826.05031 · doi:10.1007/BF01200760 |
| [232] | Slater P (1961) Inconsistencies in a schedule of paired comparisons. Biometrika 48:303312 |
| [233] | Smith WD (2007) http://rangevoting.org/PuzzDG.html |
| [234] | Smith AFM, Payne CD (1974) An algorithm for determining Slater’s i and all nearest adjoining orders. Br J Math Stat Psychol 27:4952 |
| [235] | Spencer J (1971) Optimal ranking of tournaments. Networks 1:135–138 · Zbl 0236.05110 · doi:10.1002/net.3230010204 |
| [236] | Spencer J (1978) Nonconstructive methods in discrete mathematics. In: Rota GC (eds). Studies in combinatorics. Mathematical Association of America, Washington DC, pp. 142–178 · Zbl 0407.05001 |
| [237] | Spencer J (1987) Ten lectures on the probabilistic method. CBMS-NSF regional conference series in applied mathematics N{\(\deg\)} 52, SIAM, Philadelphy |
| [238] | Stearns R (1959) The voting problem. Am Math Monthly 66:761–763 · Zbl 0090.25101 · doi:10.2307/2310461 |
| [239] | 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 |
| [240] | Thomassen C (1975) Transversals of circuits in the lexicographic product of directed graphs. Mathématiques et Sciences Humaines 51:43–45 · Zbl 0315.05109 |
| [241] | Thomassen C (1987) Counterexamples to Adám’s conjecture on arc reversals in directed graphs. J Comb Theory 42, series B:128–130 · Zbl 0609.05041 · doi:10.1016/0095-8956(87)90068-2 |
| [242] | Tucker AW (1960) On directed graphs and integer programs. In: 1960 symposium on combinatorial problems, Princeton University, Princeton |
| [243] | Tüshaus U (1983) Aggregation binärer Relationen in der qualitativen Datenanalyse. Mathematical Systems in Economics 82, Verlagsgruppe Athenäum/Hain/Hanstein · Zbl 0525.62003 |
| [244] | van Zuylen A (2005) Deterministic approximation algorithms for ranking and clusterings. Cornell ORIE Tech. Report No. 1431 |
| [245] | Vazirani VV (2003) Approximation algorithms. Springer, Berlin |
| [246] | Wakabayashi Y (1986) Aggregation of binary relations: algorithmic and polyhedral investigations, PhD thesis, Augsburg university · Zbl 0606.68036 |
| [247] | Wakabayashi Y (1998) The Complexity of Computing Medians of Relations. Resenhas 3(3):323–349 · Zbl 1098.68618 |
| [248] | Wei T (1952) The Algebraic Foundations of ranking Theory. Ph D thesis, Cambridge University, Cambridge |
| [249] | Wessels H (1981) Triangulation und Blocktriangulation von Input-Output Tabellen. Deutsches Institut für Wirtschaftsforschung: Beiträge zur Strukturforshung, Heft 63, Berlin |
| [250] | Woeginger GJ (2003) Banks winners in tournaments are difficult to recognize. Soc Choice Welfare 20(3):523–528 · Zbl 1073.05538 · doi:10.1007/s003550200197 |
| [251] | Woirgard F (1997) Recherche et dénombrement des ordres médians des tournois. PhD thesis, ENST, Paris |
| [252] | Young HP (1978) On permutations and permutation polytopes. Math Program Study 8:128–140 |
| [253] | Young HP (1988) Condorcet Theory of Voting. Am Polit Sci Rev 82:1231–1244 · doi:10.2307/1961757 |
| [254] | Younger DH (1963) Minimum feedback arc sets for a directed graph. IEEE Trans Profes Tech Group Circuit Theory 10(2):238–245 · doi:10.1109/TCT.1963.1082116 |
| [255] | Zermelo E (1929) Die Berechnung der Turnier-Ergebnisse als ein maximal Problem der Warscheinlichkeistsrechnung. Math Zeitung 29:436–460 · JFM 54.0543.01 · doi:10.1007/BF01180541 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
