×

An updated survey on the linear ordering problem for weighted or unweighted tournaments. (English) Zbl 1185.90197

Summary: In this paper, we survey some results, conjectures and open problems dealing with the combinatorial and algorithmic aspects of the linear ordering problem. This problem consists in finding a linear order which is at minimum distance from a (weighted or not) tournament. We show how it can be used to model an aggregation problem consisting of going from individual preferences defined on a set of candidates to a collective ranking of these candidates.

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
91B12 Voting theory
91B14 Social choice

Software:

PORTA; LOLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adám, A. (1964). Problem. In Theory of graphs and its applications. Proc. Coll. Smolenice, Czech. Acad. Sci. Publ. · Zbl 0121.40105
[2] Adler, I., Alon, N., & Ross, S. M. (2001). On the number of Hamiltonian paths in tournaments. Random Structures and Algorithms, 18, 291–296. · Zbl 0982.05056 · doi:10.1002/rsa.1010
[3] Ailon, N., & Alon, N. (2007). Hardness of fully dense problems. Information and Computation, 205, 117–1129. · Zbl 1121.68054 · doi:10.1016/j.ic.2007.02.006
[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) (pp. 684–693). · Zbl 1192.90252
[5] Ali, I., Cook, W. D., & Kress, M. (1986). On the minimum violations ranking of a tournament. Management Science, 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 · doi:10.1007/BF02128667
[7] Alon, N. (2006). Ranking tournaments. SIAM Journal on Discrete Mathematics, 20(1), 137–142. · Zbl 1112.05043 · doi:10.1137/050623905
[8] Alon, N., & Spencer, J. (2000). The probabilistic method (2nd edn.). New York: Wiley. · Zbl 0996.05001
[9] Alspach, B. (1967). Cycles of each length in regular tournaments. Canadian Mathematical Bulletin, 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. Canadian Mathematical Bulletin, 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 E. Diday et al. (Eds.), Data analysis and informatics III (pp. 323–343). Amsterdam: North-Holland. · 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) (pp. 24–33). · Zbl 1154.90602
[13] Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., & Protasi, M. (2003). Complexity and approximation (2nd edn.). Berlin: Springer. · Zbl 0937.68002
[14] Baker, F. B., & Hubert, L. J. (1977). Applications of combinatorial programming to data analysis: seriation using asymmetric proximity measures. British Journal of Mathematical & Statistical Psychology, 30, 154–164.
[15] Bang-Jensen, J., & Gutin, G. (2001). Digraphs: theory, algorithms, and applications. London, Berlin, Heidelberg: Springer. · Zbl 0958.05002
[16] Banks, J. (1985). Sophisticated voting outcomes and agenda control. Social Choice and Welfare, 2, 295–306. · Zbl 0597.90011 · doi:10.1007/BF00649265
[17] Banks, J., Bordes, G., & Le Breton, M. (1991). Covering relations, closest orderings and Hamiltonian bypaths in tournaments. Social Choice and Welfare, 8, 355–363. · Zbl 0734.90027 · doi:10.1007/BF00183046
[18] Bar-Noy, A., & Naor, J. (1990). Sorting, minimal feedback sets, and Hamilton paths in tournaments. SIAM Journal on Discrete Mathematics, 3(1), 7–20. · Zbl 0686.68052 · doi:10.1137/0403002
[19] Barahona, F., Fonlupt, J., & Mahjoub, A. R. (1994). Compositions of graphs and polyhedra IV: acyclic spanning subgraph. SIDMA, 7(3), 390–402. · Zbl 0802.05070
[20] Barbut, M. (1966). Note sur les ordres totaux à distance minimum d’une relation binaire donnée. Mathématiques et Sciences humaines, 17, 47–48.
[21] Barthélemy, J.-P., & Monjardet, B. (1981). The median procedure in cluster analysis and social choice theory. Mathematical Social Sciences, 1, 235–267. · Zbl 0486.62057 · doi:10.1016/0165-4896(81)90041-X
[22] Barthélemy, J.-P., & Monjardet, B. (1988). The median procedure in data analysis: new results and open problems. In H. H. Bock (Ed.), Classification and related methods of data analysis. Amsterdam: North-Holland.
[23] Barthélemy, J.-P., Guénoche, A., & Hudry, O. (1989). Median linear orders: heuristics and a branch and bound algorithm. European Journal of Operational Research, 41, 313–325. · Zbl 0689.90003 · doi:10.1016/0377-2217(89)90442-6
[24] Barthélemy, J.-P., Hudry, O., Isaak, G., Roberts, F. S., & Tesman, B. (1995). The reversing number of a digraph. Discrete Applied Mathematics, 60, 39–76. · Zbl 0826.05032 · doi:10.1016/0166-218X(94)00042-C
[25] Barthélemy, J.-P., Cohen, G., & Lobstein, A. (1996). Algorithmic complexity and communication problems. London: UCL Press. · Zbl 0765.68005
[26] Bartholdi, J.J. III, Tovey, C.A., & Trick, M.A. (1989). Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6, 157–165. · Zbl 0672.90004 · doi:10.1007/BF00303169
[27] Becker, O. (1967). Das Helmstädtersche Reihenfolgeproblem–die Effizienz verschiedener Näherungsverfahren. In: Computers uses in the social science. Vienna.
[28] Belloni, A., & Lucena, A. (2004). Lagrangian heuristics for the linear ordering problem. In M. G. C. Resende & J. P. de Sousa (Eds.), Metaheuristics: computer decision making (pp. 37–63). Dordrecht: Kluwer Academic.
[29] Berge, C. (1985). Graphs. Amsterdam: North-Holland. · Zbl 0566.05001
[30] Berger, B., & Shor, P. W. (1997). Tight bounds for the maximum acyclic subgraph problem. Journal of Algorithms, 25, 1–18. · Zbl 0888.68088 · doi:10.1006/jagm.1997.0864
[31] Berger, B., & Shor, P. W. (1990). Approximation algorithms for the maximum acyclic subgraph problem. In Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms (SODA) (pp. 236–243). · Zbl 0800.68607
[32] Bermond, J.-C. (1972). Ordres à distance minimum d’un tournoi et graphes partiels sans circuits maximaux. Mathématiques et Sciences humaines, 37, 5–25. · Zbl 0239.05122
[33] Bermond, J.-C. (1975). The circuit-hypergraph of a tournament. In Infinite and finite sets, proceedings of the colloquia mathematica societatis János Bolyai (Vol. 10, pp. 165–180). Amsterdam: North-Holland,
[34] Bermond, J.-C., & Kodratoff, Y. (1976). Une heuristique pour le calcul de l’indice de transitivité d’un tournoi. RAIRO, 10(3), 83–92.
[35] Bertacco, L., Brunetta, L., & Fischetti, M. (2008). The Linear Ordering Problem with Cumulative Costs. European Journal of Operational Research, 189, 1345–1357. · Zbl 1146.90497 · doi:10.1016/j.ejor.2006.03.071
[36] Black, D. (1958). The theory of committees and elections. Cambridge: Cambridge University Press. · Zbl 0091.15706
[37] Blin, J. M., & Whinston, A. B. (1974). A note on majority rule under transitivity constraints. Management Science, 20, 1439–1440. · Zbl 0363.90006 · doi:10.1287/mnsc.20.11.1439
[38] Blin, J. M., & Whinston, A. B. (1975). Discriminant functions and majority voting. Management Science, 21, 1029–1041. · Zbl 0318.62043 · doi:10.1287/mnsc.21.5.557
[39] Boenchendorf, K. (1982). Mathematical systems in economics : Vol. 74. Reihenfolgenprobleme/mean-flow-time sequencing. Königstein: Verlagsgruppe Athanäum/Hain/Scriptor/Hanstein.
[40] Bolotashvili, G., Kovalev, M., & Girlich, E. (1999). New facets of the linear ordering polytope. SIAM Journal on Discrete Mathematics, 12(3), 326–336. · Zbl 0966.90085 · doi:10.1137/S0895480196300145
[41] Borda, J.-C. (chevalier de) (1784). Mémoire sur les élections au scrutin. Histoire de l’Académie Royale des Sciences pour 1781, Paris.
[42] Bowman, V. J., & Colantoni, C. S. (1973). Majority rule under transitivity constraints. Management Science, 19, 1029–1041. · Zbl 0285.90003 · doi:10.1287/mnsc.19.9.1029
[43] Brualdi, R. A., & Qiao, L. (1983). Upsets in round robin tournaments. Journal of Combinatorial Theory Series B, 35, 62–77. · Zbl 0519.05033 · doi:10.1016/0095-8956(83)90080-1
[44] Brualdi, R. A., & Qiao, L. (1984). The interchange graph of tournaments with the same score vector. In Progress in graph theory (pp. 129–151). San Diego: Academic Press. · Zbl 0553.05039
[45] Buchheim, C., Wiegele, A., & Zheng, L. (2009). Exact algorithms for the quadratic linear ordering problem. Informs Journal on Computing (to appear). · Zbl 1243.90168
[46] Burkard, R. E., Çela, E., Pardalos, P. M., & Pitsoulis, L. S. (1998). The quadratic assignment problem. In P. M. Pardalos & D.-Z. Du (Eds.), Handbook of combinatorial optimization (pp. 241–338). Dordrecht: Kluwer Academic. · Zbl 0944.90071
[47] Burkov, V. N., & Groppen, V. O. (1972). Branch cuts in strongly connected graphs and permutation potentials. Automation and Remote Control, 6, 111–119. · Zbl 0252.90055
[48] Busch, A. H. (2006). A note on the number of Hamiltonian paths in strong tournaments. Electronic Journal of Combinatorics, 13, #N3. · Zbl 1080.05038
[49] Campos, V., Laguna, M., & Martí, R. (1999). Scatter search for the linear ordering problem. In D. Corne, M. Dorigo, & F. Glover (Eds.), New ideas in optimization (pp. 331–339). New York: McGraw-Hill.
[50] Campos, V., Glover, F., Laguna, M., & Martí, R. (2001). An experimental evaluation of a scatter search for the linear ordering problem. Journal of Global Optimization, 21(4), 397–414. · Zbl 1175.90424 · doi:10.1023/A:1012793906010
[51] Campos, V., Laguna, M., & Martí, R. (2005). Context-independent scatter and tabu search for permutation problems. INFORMS Journal on Computing, 17(1), 331–339. · Zbl 1239.90109 · doi:10.1287/ijoc.1030.0057
[52] Caspard, N., Monjardet, B., & Leclerc, B. (2007). Ensembles ordonnés finis : concepts, résultats et usages. Berlin: Springer. · Zbl 1136.06001
[53] Chanas, S., & Kobylanski, P. (1996). A new heuristic algorithm solving the linear ordering problem. Computational Optimization and Applications, 6, 191–205. · Zbl 0860.90100
[54] Chaovalitwongse, W., Pardalos, P. M., Resende, M. G. C., & Grundel, D. A. (2009). Revised GRASP with path-relinking for the linear ordering problem. Submitted for publication to the Journal of Combinatorial Optimization, and AT&T Labs Research technical report. · Zbl 1236.90100
[55] Charbit, P., Thomasse, S., & Yeo, A. (2007). The minimum feedback arc set problem is NP-hard for tournaments. Combinatorics, Probability and Computing, 16(1), 1–4. · Zbl 1120.05038 · doi:10.1017/S0963548306007887
[56] Charon, I., & Hudry, O. (1998). Lamarckian genetic algorithms applied to the aggregation of preferences. Annals of Operations Research, 80, 281–297. · Zbl 0907.90009 · doi:10.1023/A:1018976217274
[57] Charon, I., & Hudry, O. (2000). Slater orders and Hamiltonian paths of tournaments. Electronic Notes in Discrete Mathematics, 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. European Journal of Operational Research, 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, Seriia 2, 8(2), 73–91 (in Russian).
[60] Charon, I., & Hudry, O. (2002). The noising methods: a survey. In P. Hansen & C. C. Ribeiro (Eds.), Essays and surveys in metaheuristics (pp. 245–261). Dordrecht: Kluwer Academic. · Zbl 1005.90051
[61] Charon, I., & Hudry, O. (2003). Links between the Slater index and the Ryser index of tournaments. Graphs and Combinatorics, 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. Discrete Applied Mathematics, 154, 2097–2116. · Zbl 1111.90121 · doi:10.1016/j.dam.2005.04.020
[63] Charon, I., & Hudry, O. (2007). A survey on the linear ordering problem for weighted or unweighted tournaments, 4OR, 5(1), 5–60. · Zbl 1126.05052 · doi:10.1007/s10288-007-0036-6
[64] Charon, I., & Hudry, O. (2009a). Self-tuning of the noising methods. Optimization, 58(7), 1–21. · Zbl 1189.90105 · doi:10.1080/02331930902944911
[65] Charon, I., & Hudry, O. (2009b). Branch and bound. In V. Paschos (Ed.) Handbook of combinatorial optimization. Wiley, New York (to appear) · Zbl 1189.90105
[66] Charon, I., & Hudry, O. (2009c). Maximum distance between Slater orders and Copeland orders of tournaments (submitted for publication). · Zbl 1214.05038
[67] Charon, I., & Hudry, O. (2009d). How different can Slater’s solutions and Kemeny’s solutions of tournaments be? (submitted for publication).
[68] Charon, I., Germa, A., & Hudry, O. (1992a). Encadrement de l’indice de Slater d’un tournoi à l’aide de ses scores. Mathématiques, Informatique et Sciences humaines, 118, 53–68. · Zbl 0846.05040
[69] Charon, I., Germa, A., & Hudry, O. (1992b). Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois. Mathématiques, Informatique et Sciences humaines, 119, 53–74. · Zbl 0845.05050
[70] Charon, I., Germa, A., & Hudry, O. (1996a). Random generation of tournaments and asymmetric digraphs with given out-degrees. European Journal of Operational Research, 95, 411–419. · Zbl 0974.05502 · doi:10.1016/0377-2217(95)00294-4
[71] 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 (pp. 309–318). Berlin: Springer · Zbl 0897.90003
[72] 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
[73] Charon, I., Guénoche, A., Hudry, O., & Woirgard, F. (1997a). New results on the computation of median orders. Discrete Mathematics, 165–166, 139–154. · Zbl 0878.68090 · doi:10.1016/S0012-365X(96)00166-5
[74] Charon, I., Hudry, O., & Woirgard, F. (1997b). A 16-vertex tournament for which Banks set and Slater set are disjoint. Discrete Applied Mathematics, 80(2–3), 211–215. · Zbl 0895.05027 · doi:10.1016/S0166-218X(97)88689-1
[75] Chartrand, G., Geller, D., & Hedetniemi, S. (1971). Graphs with forbidden subgraphs. Journal of Combinatorial Theory, Series B, 10(1), 12–41. · Zbl 0223.05101 · doi:10.1016/0095-8956(71)90065-7
[76] Chenery, H. B., & Watanabe, T. (1958). International comparisons of the structure of production. Econometrica, 26(4), 487–521. · doi:10.2307/1907514
[77] Chiarini, B., Chaovalitwongse, W., & Pardalos, P. M. (2004). A new algorithm for the triangulation of input-output tables. In P. M. Pardalos, A. Migdalas, & G. Baourakis (Eds.), Supply chain and finance (pp. 254–273). Singapore: World Scientific.
[78] Christof, T., & Reinelt, G. (1996). Combinatorial optimization and small polytopes. Top, 4(1), 1–64. · Zbl 0858.90107 · doi:10.1007/BF02568602
[79] Christof, T., & Reinelt, G. (1997a). Low-dimensional linear ordering polytopes. Working paper, University of Heidelberg.
[80] Christof, T., & Reinelt, G. (1997b). Small instances relaxations for solving linear ordering problems by branch-and-cut (Technical report). University of Heidelberg.
[81] Christof, T., & Reinelt, G. (2001). Algorithmic aspects of using small instance relaxations in parallel branch-and-cut. Algorithmica, 30(4), 507–629. · Zbl 0973.90064 · doi:10.1007/s00453-001-0029-3
[82] 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
[83] Cohen, W., Schapire, R., & Singer, Y. (1999). Learning to order things. Journal of Artificial Intelligence Research, 10, 213–270. · Zbl 0915.68031
[84] Condorcet, M. J. A. N. Caritat (marquis de) (1785). Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix, Paris.
[85] Congram, R. K. (2000). Polynomially searchable exponential neighbourhoods for sequencing problems in combinatorial optimisation. Ph.D. thesis, University of Southampton.
[86] Conitzer, V. (2006). Computing Slater rankings using similarities among candidates. In Proceedings of the 21st national conference on artificial intelligence (AAAI-06), Boston, MA, USA (pp. 613–619). Early version: IBM research report RC23748, 2005.
[87] Cook, W. D., & Saipe, A. L. (1976). Committee approach to priority planning: the median ranking method. Cahiers du Centre d’Études et de Recherche Opérationnelle 18(3), 337–352. · Zbl 0348.90088
[88] Cook, W. D., Golan, I., & Kress, M. (1988). Heuristics for ranking players in a round robin tournament. Computers and Operations Research, 15(2), 135–144. · doi:10.1016/0305-0548(88)90006-8
[89] Cook, W. D., Doyle, J., Green, R., & Kress, M. (1996). Ranking players in multiple tournaments. Computers and Operations Research, 23(9), 869–880. · Zbl 0859.90004 · doi:10.1016/0305-0548(95)00082-8
[90] Copeland, A. H. (1951). A ”reasonable” social welfare function. Seminar on applications of mathematics to social sciences, University of Michigan.
[91] Coppersmith, D., & Winograd, S. (1990). Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9, 251–280. · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2
[92] 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
[93] Czygrinow, A., Poljak, S., & Rödl, V. (1999). Constructive quasi-Ramsey numbers and tournament ranking. SIAM Journal on Discrete Mathematics, 12(1), 48–63. · Zbl 0933.68099 · doi:10.1137/S0895480197318301
[94] 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).
[95] de Cani, J. S. (1969). Maximum likelihood paired comparison ranking by linear programming. Biometrika, 3, 537–545. · Zbl 0188.50101
[96] de Cani, J. S. (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
[97] de la Vega, W. F. (1983). On the maximal cardinality of a consistent set of arcs in a random tournament. Journal of Combinatorial Theory Series B, 35, 328–332. · Zbl 0531.05036
[98] 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.
[99] Debord, B. (1987b). Axiomatisation de procédures d’agrégation de préférences. Ph.D. thesis, Université scientifique technologique et médicale de Grenoble.
[100] Dixon, J. D. (1967). The maximum order of the group of a tournament. Canadian Mathematical Bulletin, 10, 503–505. · Zbl 0203.01501 · doi:10.4153/CMB-1967-048-9
[101] Dodgson, C. L. (1876). A method of taking votes on more than two issues. Oxford: Clarendon.
[102] Doignon, J.-P., Fiorini, S., & Joret, G. (2006). Facets of the linear ordering polytope: a unification for the fence family through weighted graphs. Journal of Mathematical Psychology, 50/3, 251–262. · Zbl 1096.05050 · doi:10.1016/j.jmp.2006.01.001
[103] Dom, M., Guo, J., Hüffner, F., Niedermeier, R., & Truß, A. (2006). Lecture notes in computer science : Vol. 3998. Fixed-parameter tractability results for feedback set problems in tournaments (pp. 320–331). Heidelberg: Springer. · Zbl 1183.68419
[104] Downey, R. G., & Fellows, M. R. (1999). Parameterized complexity. Berlin: Springer. · Zbl 0961.68533
[105] Dréo, J., Petrowski, A., Taillard, E., & Siarry, P. (2006). Metaheuristics for hard optimization. Methods and case studies. Berlin: Springer. · Zbl 1118.90058
[106] Duarte, A., Laguna, M., & Marti, R. (2009). Tabu search for the linear ordering problem with cumulative costs. Computational Optmization and Applications (to appear).
[107] Dugat, V. (1990). Décomposition de tournois réguliers: théorie et application aux algorithmes de tests d’isomorphisme. Ph.D. thesis, Université Paul Sabatier, Toulouse.
[108] Dutta, B. (1988). Covering sets and a new Condorcet choice correspondence. Journal of Economic Theory, 44, 63–80. · Zbl 0652.90013 · doi:10.1016/0022-0531(88)90096-8
[109] 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).
[110] Eades, P., & Lin, X. (1995). A new heuristic for the feedback arc set problem. Australian Journal of Combinatorics, 12, 15–26. · Zbl 0838.68086
[111] Eades, P., Lin, X., & Smyth, W. F. (1993). A fast and effective heuristic for the feedback arc set problem. Information Processing Letters, 47(6), 319–323. · Zbl 0787.68078 · doi:10.1016/0020-0190(93)90079-O
[112] Erdös, P. & Moon, J. W. (1965). On sets of consistent arcs in a tournament. Canadian Mathematical Bulletin, 8, 269–271. · Zbl 0137.43301 · doi:10.4153/CMB-1965-017-1
[113] Erdös, P., & Moser, L. (1964). On the representation of directed graphs as unions of orderings. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei. 9, 125–132.
[114] Even, G., Naor, J. S., 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
[115] Even, G., Naor, J. S., Rao, S., & Schieber, B. (2000). Divide-and-conquer approximation algorithms via spreading metrics. Journal of the ACM, 47, 585–616. · Zbl 1303.68156 · doi:10.1145/347476.347478
[116] Fagin, R., Kumar, R., Mahdian, M., Sivakumar, D., & Vee, E. (2005). Rank aggregation: an algorithmic perspective. Unpublished manuscript. · Zbl 1414.91126
[117] Festa, P., Pardalos, P., & Resende, M. (1999). Feedback set problems. In D. Z. Du & P. M. Pardalos (Eds.), Handbook of combinatorial optimization (Vol. 4, pp. 209–258). Dordrecht: Kluwer Academic. · Zbl 1253.90193
[118] Fiorini, S. (2001a). Polyhedral combinatorics of order polytopes. Ph.D. thesis, Université libre de Bruxelles. · Zbl 1006.20002
[119] Fiorini, S. (2001b). Determining the automorphism group of the linear ordering polytope. Discrete Applied Mathematics, 112/1–3, 121–128. · Zbl 1006.20002 · doi:10.1016/S0166-218X(00)00312-7
[120] Fiorini, S. (2006a). How to recycle your facets. Discrete Optimization, 3/2, 136–153. · Zbl 1146.90478 · doi:10.1016/j.disopt.2005.10.007
[121] Fiorini, S. (2006b). {0,1/2}-cuts and the linear ordering problem: surfaces that define facets. SIAM Journal on Discrete Mathematics, 20/4, 893–912. · Zbl 1126.05081 · doi:10.1137/S0895480104440985
[122] Fiorini, S., & Fishburn, P. (2003). Facets of linear signed order polytopes. Discrete Applied Mathematics, 131/3, 597–610. · Zbl 1077.91017 · doi:10.1016/S0166-218X(03)00224-5
[123] Fishburn, P. (1977). Condorcet social choice functions. SIAM Journal of Applied Mathematics, 33, 469–489. · Zbl 0369.90002 · doi:10.1137/0133030
[124] Fishburn, P. (1992). Induced binary probabilities and the linear ordering polytope: a status report. Mathematical Social Sciences, 23, 67–80. · Zbl 0751.90004 · doi:10.1016/0165-4896(92)90038-7
[125] Flood, M. M. (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
[126] Flueck, J. A., & Korsh, J. F. (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
[127] Fulkerson, D. R. (1965). Upsets in round robin tournaments. Canadian Journal of Mathematics, 17, 957–969. · Zbl 0135.01304 · doi:10.4153/CJM-1965-091-7
[128] Gamboa, D., Rego, C., & Glover, F. (2006). A relax-and-cut RAMP approach for the linear ordering problem. In the abstracts booklet of ECCO XIX/CO2006 Joint Meeting, Porto, Portugal, p. 40. · Zbl 1079.90110
[129] Garcia, C. G., Perez-Brito, D., Campos, V., & Marti, R. (2006). Variable neighborhood search for the linear ordering problem. Computers and Operations Research, 33(12), 3549–3565. · Zbl 1094.90039 · doi:10.1016/j.cor.2005.03.032
[130] Garey, M. R., & Johnson, D. S. (1979). Computers and intractability, a guide to the theory of NP-completeness. New York: Freeman. · Zbl 0411.68039
[131] 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.
[132] Glover, F., & Kochenberger, G. A. (2003). Handbook of metaheuristics. Dordrecht: Kluwer Academic. · Zbl 1058.90002
[133] Glover, F., Klastorin, T., & Klingman, D. (1974). Optimal weighted ancestry relationships. Management Science, 20, 1190–1193. · Zbl 0303.90055 · doi:10.1287/mnsc.20.8.1190
[134] Goddard, S. T. (1983). Tournament rankings. Management Science, 29(12), 1385–1392. · Zbl 0527.90047 · doi:10.1287/mnsc.29.12.1384
[135] Goemans, M. X., & Hall, L. A. (1996). The strongest facets of the acyclic subgraph polytope are unknown. In W. H. Cunningham, S. T. McCormick, & M. Queyranne (Eds.), Lecture notes in computer science : Vol. 1084. Integer programming and optimization (pp. 415–429). Berlin: Springer.
[136] Goldberg, M. (1966). Results on the automorphism group of a graph. M.Sc. Thesis, university of Alberta.
[137] Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Reading: Addison-Wesley. · Zbl 0721.68056
[138] González, C. G., & 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).
[139] Greistorfer, P. (2004). Experimental pool design: input, output and combination strategies for scatter search. In M. G. C. Resende & J. P. de Sousa (Eds.), Metaheuristics: computer decision making (pp. 279–300). Dordrecht: Kluwer Academic.
[140] Grindberg, E., & Dambit, Y. (1965). Some properties of graphs containing circuits. Latvijskij Matematičeskij Ežegodnik (pp. 65–70) (in Russian).
[141] Grötschel, M., Jünger, M., & Reinelt, G. (1984a). A cutting plane algorithm for the linear ordering problem. Operations Research, 32, 1195–1220. · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195
[142] 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
[143] Grötschel, M., Jünger, M., & Reinelt, G. (1985a). On the acyclic subgraph polytope. Mathematical Programming, 33, 1–27. · Zbl 0562.90095 · doi:10.1007/BF01582008
[144] Grötschel, M., Jünger, M., & Reinelt, G. (1985b). Facets of the linear ordering polytope. Mathematical Programming, 33, 43–60. · Zbl 0577.05035 · doi:10.1007/BF01582010
[145] Grötschel, M., Jünger, M., & Reinelt, G. (1985c). Acyclic subdigraphs and linear orderings: polytopes, facets, and a cutting plane algorithm. In I. Rival (Ed.), Graphs and orders (pp. 217–264). Dordrecht: Reidel. · Zbl 0565.90044
[146] Guénoche, A. (1977). Un algorithme pour pallier l’effet Condorcet. RAIRO, 11(1), 77–83. · Zbl 0356.90068
[147] 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.
[148] 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.
[149] Guénoche, A. (1996). Vainqueurs de Kemeny et tournois difficiles. Mathématiques, Informatique et Sciences humaines, 133, 57–66. · Zbl 0870.90096
[150] 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
[151] Guénoche, A. (1995). How to choose according to partial evaluations. In B. Bouchon-Meunier et al. (Ed.), Lecture notes in computer sciences : Vol. 945. Advances in intelligent computing, IPMU’94 (pp. 611–618). Berlin-Heidelberg: Springer.
[152] Guilbaud, G. T. (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.
[153] Guy, R. K. (1967). A coarseness conjecture of Erdös. Journal of Combinatorial Theory, 3, 38–42. · Zbl 0149.41501 · doi:10.1016/S0021-9800(67)80014-0
[154] Hansen, M. (1989). Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In Proceedings of the 30th annual symposium on foundations of computer science (pp. 604–609). Los Alamitos: IEEE Computer Society.
[155] Hardouin Duparc, J. (1975). Quelques résultats sur l’ “indice de transitivité {” de certains tournois. Mathématiques et Sciences humaines, 51, 35–41.}
[156] Hassin, R., & Rubinstein, S. (1994). Approximations for the maximum acyclic subgraph problem. Information Processing Letters, 51(3), 133–140. · Zbl 0942.68644 · doi:10.1016/0020-0190(94)00086-7
[157] Hemaspaandra, L. (2000). Complexity classes. In K. H. Rosen (Ed.), Handbook of discrete and combinatorial mathematics (pp. 1085–1090). Boca Raton: CRC Press.
[158] Hemaspaandra, E., Spakowski, H., & Vogel, J. (2005). The complexity of Kemeny elections. Theoretical Computer Science, 349, 382–391. · Zbl 1086.68046
[159] Huang, G., & Lim, A. (2003). Designing a hybrid genetic algorithm for the linear ordering problem. In LNCS : Vol. 2723. Proceedings of ”genetic and evolutionary computation conference (GECCO) 2003”, part I (pp. 1053–1064). Berlin: Springer. · Zbl 1028.68780
[160] Huber, L. (1976). Seriation using asymmetric proximity measures. British Journal of Mathematical & Statistical Psychology, 29, 32–52. · Zbl 0334.92040
[161] 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
[162] Hudry, O. (1989). Recherche d’ordres médians : complexité, algorithmique et problèmes combinatoires. Ph.D. thesis, ENST, Paris.
[163] Hudry, O. (1997a). Algorithms for the aggregation of ordinal preferences: a review. In Proceedings of the first conference on operations and quantitative management (ICOQM), Jaipur, India (pp. 169–176).
[164] 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
[165] Hudry, O. (1998). Tournois et optimisation combinatoire. Habilitation à diriger des recherches, université Paris 6, Paris, 1998.
[166] Hudry, O. (2004). A note on ”Banks winners in tournaments are difficult to recognize” by G. J. Woeginger. Social Choice and Welfare, 23, 113–114. · Zbl 1088.91506 · doi:10.1007/s00355-003-0241-y
[167] Hudry, O. (2008). NP-hardness results on the aggregation of linear orders into median orders. Annals of Operations Research, 163(1), 63–88. · Zbl 1192.68296 · doi:10.1007/s10479-008-0353-y
[168] Hudry, O. (2009a). A survey on the complexity of tournament solutions. Mathematical Social Sciences, 57, 292–303. · Zbl 1176.91030 · doi:10.1016/j.mathsocsci.2008.12.002
[169] Hudry, O. (2009b). Complexity of voting procedures. In R. Meyers (Ed.), Encyclopedia of complexity and systems science. New York: Springer.
[170] Hudry, O. (2009c). Complexity of Kemeny’s problems (submitted for publication).
[171] Hudry, O. (2010). On the complexity of Slater’s problems. European Journal of Operational Research 203, 216–221. · Zbl 1176.90606 · doi:10.1016/j.ejor.2009.07.034
[172] Hudry, O., Leclerc, B., Monjardet, B., & Barthélemy, J.-P. (2009). Metric and latticial medians. In D. Dubois, M. Pirlot, D. Bouyssou and H. Prade (Eds.), Concepts and methods for decision aid (pp. 763–803). Hermès (to appear).
[173] Isaak, G. (1995). Tournaments as feedback arc sets. The Electronic Journal of Combinatorics, 2, R20. · Zbl 0829.68100
[174] Isaak, G., & Tesman, B. (1991). The weighted reversing number of a digraph. Congressus Numerantium, 83, 115–124. · Zbl 0768.05046
[175] Jacquet-Lagrèze É. (1969). L’agrégation des opinions individuelles. Informatique et Sciences humaines, 4, 1–21.
[176] 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 (pp. 675–677). Amsterdam: North-Holland. · Zbl 0207.23002
[177] Jünger, M. (1985). Polyhedral combinatorics and the acyclic subdigraph problem. Berlin: Heldermann. · Zbl 0557.68045
[178] Kaas, R. (1981). A branch and bound algorithm for the acyclic subgraph problem. European Journal of Operational Research, 8, 355–362. · Zbl 0465.90090 · doi:10.1016/0377-2217(81)90005-9
[179] Kadane, J. B. (1966). Some equivalence classes in paired comparisons. Annals of Mathematical Statistics, 37, 488–494. · Zbl 0171.40101 · doi:10.1214/aoms/1177699532
[180] Kano, M., & Sakamoto, A. (1985). Ranking the vertices of a paired comparison digraph. SIAM Journal on Algebraic and Discrete Methods, 6(1), 79–92. · Zbl 0572.05030 · doi:10.1137/0606009
[181] Karp, R. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Tatcher (Eds.), Complexity of computer computations (pp. 85–103). New York: Plenum.
[182] Kaykobad, M., Ahmed, Q. N. U., Shafiqul Khalid, A. T. M., & Bakhtiar, R.-A. (1995). A new algorithm for ranking players of a round-robin tournament. Computers and Operations Research, 22(2), 221–226. · Zbl 0814.90147 · doi:10.1016/0305-0548(94)E0024-2
[183] Kemeny, J. G. (1959). Mathematics without numbers. Daedalus, 88, 577–591.
[184] Kendall, M. G. (1938). Rank correlation methods. New York: Hafner. · Zbl 0019.13001
[185] Kendall, M. G., & Babington Smith, B. (1940). On the method of paired comparisons. Biometrika, 33, 239–251. · Zbl 0063.03216 · doi:10.1093/biomet/33.3.239
[186] Klamler, C. (2003). Kemeny’s rule and Slater’s rule: a binary comparison. Economics Bulletin, 4(35), 1–7.
[187] Klamler, C. (2004). The Dodgson ranking and its relation to Kemeny’s method and Slater’s rule. Social Choice and Welfare, 23, 91–102. · Zbl 1088.91023 · doi:10.1007/s00355-003-0238-6
[188] Koppen, M. (1995). Random utility representation of binary choice probabilities: critical graphs yielding critical necessary conditions. Journal of Mathematical Psychology, 19, 21–39. · Zbl 0897.92045 · doi:10.1006/jmps.1995.1003
[189] Korte, B. (1979). Approximation algorithms for discrete optimization problems. Annals of Discrete Mathematics, 4, 85–120. · Zbl 0411.90052 · doi:10.1016/S0167-5060(08)70820-3
[190] Korte, B., & Oberhofer, W. (1968). Zwei Algorithmen zur Lösung eines komplexen Reihenfolgeproblems. Unternehmensforschung, 12, 217–231. · Zbl 0167.18403 · doi:10.1007/BF01918332
[191] Korte, B., & Oberhofer, W. (1969). Zur Triangulation von Input-Output-Matrizen. Jahrbucher für Nationaloekonomie und Statistik, 182, 398–433.
[192] Kotzig, A. (1975). On the maximal order of cyclicity of antisymmetric directed graphs. Discrete Mathematics, 12, 17–25. · Zbl 0299.05107 · doi:10.1016/0012-365X(75)90092-8
[193] Lad, A., Ghani, R., Yang, Y., & Kisiel, B. (2009). Towards optimal ordering of prediction tasks. SIAM international conference on data mining (SDM09) (pp. 883–893).
[194] Laffond, G., & Laslier, J.-F. (1991). Slater’s winners of a tournament may not be in the Banks set. Social Choice and Welfare, 8, 355–363. · Zbl 0733.90008 · doi:10.1007/BF00183047
[195] Laffond, G., Laslier, J.-F., & Le Breton, M. (1993). The Bipartisan set of a tournament game. Games and Economic Behavior, 5, 182–201. · Zbl 0770.90080 · doi:10.1006/game.1993.1010
[196] Laffond, G., Laslier, J.-F., & Le Breton, M. (1991a). Choosing from a tournament: a progress report and some new results (Technical report). CNAM, Paris.
[197] Laffond, G., Laslier, J.-F., & Le Breton, M. (1991b). A game-theoretical method for ranking the participants in a tournament (Technical report). CNAM, Paris.
[198] Laguna, M., Marti, R., & Campos, V. (1999). Intensification and diversification with elite tabu search solutions for the linear ordering problem. Computers and Operations Research, 26(12), 1217–1230. · Zbl 1016.90081 · doi:10.1016/S0305-0548(98)00104-X
[199] Landau, H. G. (1953). On dominance relations and the structure of animal societies III. The condition for a score structure. Bulletin of Mathematical Biophysics, 13, 1–19. · doi:10.1007/BF02478336
[200] Laslier, J.-F. (1997). Tournament solutions and majority voting. Berlin, Heidelberg, New York: Springer. · Zbl 0948.91504
[201] Lawler, E. L. (1964). A comment on minimum feedback arc sets. IEEE Transactions on Circuit Theory, 11, 296–297.
[202] 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).
[203] Lemaréchal, C. (2003). The omnipresence of Lagrange. 4OR, 1(1), 7–25. · Zbl 1046.90064
[204] Lempel, A., & Cederbaum, I. (1966). Minimum feedback arc and vertex sets of a directed graph. IEEE Transactions on Circuit Theory, 13, 399–403. · Zbl 0191.55303 · doi:10.1109/TCT.1966.1082620
[205] Lenstra, J. K. (1977). Mathematical centre tracts : Vol. 69. Sequencing by enumerative methods. Amsterdam: Mathematisch Centrum. · Zbl 0407.90025
[206] Lenstra, H. W. Jr. (1973). The acyclic subgraph problem (Technical report BW26). Mathematisch Centrum, Amsterdam. · Zbl 0304.90112
[207] Leung, J., & Lee, J. (1994). More facets from fences for linear ordering and acyclic subgraph polytopes. Discrete Applied Mathematics, 50, 185–200. · Zbl 0817.52017 · doi:10.1016/0166-218X(92)00151-B
[208] 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).
[209] Marcotorchino, J.-F., & Michaud, P. (1979). Optimisation en analyse ordinale de données. Paris: Masson.
[210] Matoušek, J., & Nešetřil, J. (1998). Invitation to discrete mathematics. London: Clarendon Press, Oxford University Press.
[211] McGarvey, D. (1953). A theorem on the construction of voting paradoxes. Econometrica, 21, 608–610. · doi:10.2307/1907926
[212] McKey, B. (2006). http://cs.anu.edu.au/\(\sim\)bdm/data/digraphs.html .
[213] McLean, I. (1995). The first golden age of social choice, 1784–1803. In W. A. Barnett, H. Moulin, M. Salles, & N. J. Schofield (Eds.), Social choice, welfare, and ethics: proceedings of the eighth international symposium in economic theory, econometrics (pp. 13–33). Cambridge: Cambridge University Press. · Zbl 0881.90007
[214] McLean, I., & Hewitt, F. (1994). Condorcet: foundations of social choice and political theory. Cheltenham Glos: Edward Elgar.
[215] McLean, I., & Urken, A. (1995). Classics of social choice. Ann Arbor: University of Michigan Press.
[216] McLean, I., & Urken, A. (1997). La réception des oeuvres de Condorcet sur le choix social (1794–1803) : Lhuilier, Morales et Daunou. In A.-M. Chouillet, P. Crépel (Eds.), Condorcet, homme des lumières et de la révolution (pp. 147–160). ENS éditions, Fontenay-aux-roses.
[217] McLean, I., Lorrey, H., & Colomer, J. M. (2008). Social choice in medieval Europe. Electronic Journal for History of Probability and Statistics, 4(1). · Zbl 1181.01014
[218] Méndez-Díaz, I., Nasini, G., & Zabala, P. (2009). The disjunctive rank and cutting plane algorithms using of facets of the linear ordering polytope (submitted for publication).
[219] Mendonça, D., & Raghavachari, M. (2000). Comparing the efficacy of ranking methods for multiple round-robin tournaments. European Journal of Operational Research, 123, 593–605. · Zbl 1068.91507 · doi:10.1016/S0377-2217(99)00110-1
[220] Merchant, D. K., & Rao, M. R. (1976). Majority decisions and transitivity: some special cases. Management Science, 23(2), 125–130. · Zbl 0349.90002 · doi:10.1287/mnsc.23.2.125
[221] Miller, N. (1980). A new solution set for tournaments and majority voting: Further graph-theoretical approaches to the theory of voting. American Journal of Political Science, 24(1), 68–96. · doi:10.2307/2110925
[222] Mitchell, J. E. (2000). Computational experience with an interior point cutting plane algorithm. SIAM Journal on Optimization, 10(4), 1212–1227. · Zbl 0999.90050 · doi:10.1137/S1052623497324242
[223] Mitchell, J. E. (2007). Generating linear ordering problems. http://www.rpi.edu/\(\sim\)mitchj/generators/linord/ .
[224] Mitchell, J. E., & Borchers, B. (1996). Solving real world linear ordering problems using a primal-dual interior point cutting plane method. Annals of Operations Research, 62, 253–276. · Zbl 0848.90086 · doi:10.1007/BF02206819
[225] Mitchell, J. E., & Borchers, B. (2000). Solving linear ordering problems with a combined interior point/simplex cutting plane algorithm. In H. L. Frenk, K. Roos, T. Terlaky, & S. Zhang (Eds.), High performance optimization (pp. 349–366). Dordrecht: Kluwer Academic. · Zbl 0965.90057
[226] Monjardet, B. (1973). Tournois et ordres médians pour une opinion. Mathématiques et Sciences humaines, 43, 55–73. · Zbl 0271.05114
[227] Monjardet, B. (1979). Relations à éloignement minimum de relations binaires, note bibliographique. Mathématiques et Sciences humaines, 67, 115–122. · Zbl 0413.62045
[228] Monjardet, B. (1990). Sur diverses formes de la ”règle de Condorcet” d’agrégation des préférences. Mathématiques, Informatique et Sciences humaines, 111, 61–71. · Zbl 0723.01012
[229] Monsuur, H., & Storcken, T. (1997). Measuring intransitivity. Mathematical Social Sciences, 34, 125–152. · Zbl 0916.90006 · doi:10.1016/S0165-4896(97)00010-3
[230] Moon, J. W. (1968). Topics on tournaments. New York: Holt, Rinehart and Winston. · Zbl 0191.22701
[231] Nalivaiko, V. (1997). The linear ordering polytope. Preprint 39/97, Faculty of Mathematics of the Otto-von-Guericke-University of Magdeburg.
[232] Nalivaiko, V. (1999). Das lineare Ordnungsproblem. Ph.D. Thesis, Falkultät für Mathematik, Universität Magdeburg, Magdeburg, Germany, 1999.
[233] Newman, A. (2000). Approximating the maximum acyclic subgraph. Master’s thesis, MIT, USA.
[234] Newman, A. (2004). Cuts and orderings: on semidefinite relaxations for the linear ordering problem. In K. Jansen, S. Khanna, J. D. P. Rolim, & D. Ron (Eds.), Lectures notes in computer science (Vol. 3122, pp. 195–206). Berlin: Springer. · Zbl 1105.90358
[235] Newman, A., & Vempala, S. (2001). Fences are futile: on relaxations for the linear ordering problem. In Proceedings of the 8th conference on integer programming and combinatorial optimization (IPCO) (pp. 333–347). · Zbl 1010.90042
[236] Nishihara, O., Kumamoto, H., & Inoue, K. (1989). The new formulations of minimum feedback arc set problem. In C. Brexinski (Ed.), Numerical and applied mathematics. J.C. Baltzer AG, Scientific Publishing Co.
[237] Nutov, Z., & Penn, M. (1995). On the integral dicycle packings and covers and the linear ordering polytope. Discrete Applied Mathematics, 60, 293–309. · Zbl 0826.05047 · doi:10.1016/0166-218X(94)00060-Q
[238] 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
[239] Orlin, J. B. (1981). Unpublished manuscript.
[240] Östergård, P. R. J., & Vaskelainen, V. P. (2009). A tournament of order 14 with disjoint Banks and Slater sets. Discrete Applied Mathematics (to appear). · Zbl 1215.05080
[241] Papadimitriou, C., & Yannakakis, M. (1991). Optimization, approximation, and complexity classes. Journal of Computer System Science, 43, 425–440. · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X
[242] Phillips, J. P. N. (1967). A procedure for determining Slater’s i and all nearest adjoining orders. British Journal of Mathematical and Statistical Psychology, 20, 217–225.
[243] Phillips, J. P. N. (1969). A further procedure for determining Slater’s i and all nearest adjoining orders. British Journal of Mathematical and Statistical Psychology, 22, 97–101.
[244] Phillips, J. P. N. (1976). On an algorithm of Smith and Payne for determining Slater’s i and all nearest adjoining orders. British Journal of Mathematical and Statistical Psychology, 29, 126–127.
[245] Poljak, S., & Turzík, D. (1986). A polynomial time heuristic for certain subgraph optimization problems with guaranteed lower bound. Discrete Mathematics, 58, 99–104. · Zbl 0585.05032 · doi:10.1016/0012-365X(86)90192-5
[246] Poljak, S., Rödl, V., & Spencer, J. (1988). Tournament ranking with expected profit in polynomial time. SIAM Journal Discrete Mathematics, 1(3), 372–376. · Zbl 0667.05030 · doi:10.1137/0401037
[247] Raman, V., & Saurabh, S. (2006). Parameterized algorithms for feedback set problems and their duals in tournaments. Theoretical Computer Science, 351, 446–458. · Zbl 1086.68105 · doi:10.1016/j.tcs.2005.10.010
[248] Rao, S., & Richa, A. W. (2004). New approximation techniques for some linear ordering problems. SIAM Journal on Computing, 34(2), 388–404. · Zbl 1087.68130 · doi:10.1137/S0097539702413197
[249] Ratliff, T. C. (2001). A comparison of the Dodgson method and Kemeny’s rule. Social Choice and Welfare, 18, 79–90. · Zbl 1069.91536 · doi:10.1007/s003550000060
[250] Rédei, L. (1934). Ein kombinatorischer Satz. Acta. Litt. Szeged, 7, 39–43. · JFM 60.0049.01
[251] Reid, K. B. (1969). On set of arcs containing no cycles in tournaments. Canadian Mathematical Bulletin, 12, 261–264. · Zbl 0181.51901 · doi:10.4153/CMB-1969-032-x
[252] Reid, K. B. (1983). Monochromatic reachability, complementary cycles and single arc reversals in tournaments. In Lecture notes in mathematics : Vol. 1073. Graph theory, proceedings of the first Southeast Asian graph theory colloquium held in Singapore (May 1983) (pp. 11–21). Berlin: Springer.
[253] Reid, K. B. (2004). Tournaments. In J. L. Gross & J. Yellen (Eds.), Handbook of graph theory (pp. 156–184). Boca Raton: CRC Press.
[254] Reid, K. B., & Beineke, L. W. (1978). Tournaments. In L. W. Beineke & R. J. Wilson (Eds.), Selected topics in graph theory (pp. 169–204). San Diego: Academic Press. · Zbl 0434.05037
[255] Reinelt, G. (1985). Research and exposition in mathematics : Vol. 8. The linear ordering problem: algorithms and applications. Berlin: Heldermann. · Zbl 0565.68058
[256] Reinelt, G. (1993). A note on small linear-ordering polytopes. Discrete & Computational Geometry, 10, 67–78. · Zbl 0784.90063 · doi:10.1007/BF02573963
[257] Reinelt, G. (2002). Linear ordering library (LOLIB). http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/LOLIB/LOLIB.html .
[258] Remage, R., & Thompson, W. A. (1964). Rankings from paired comparison. Annals of Mathematical Statistics, 35, 739–747. · Zbl 0138.13206 · doi:10.1214/aoms/1177703572
[259] Remage, R., & Thompson, W. A. (1966). Maximum likelihood paired comparison rankings. Biometrika, 53, 143–149. · Zbl 0138.13207
[260] Righini G. (2008). A branch-and-bound algorithm for the linear ordering problem with cumulative costs. European Journal of Operational Research, 186(3), 965–971. · Zbl 1146.90529 · doi:10.1016/j.ejor.2007.02.044
[261] Rubinstein, A. (1980). Ranking the participants in a tournament. SIAM Journal of Applied Mathematics, 98, 108–111. · Zbl 0442.05028 · doi:10.1137/0138009
[262] Ryser, H. J. (1964). Matrices of zeros and ones in combinatorial mathematics. In Recent advances in matrix theory (pp. 103–124). Madison: University of Wisconsin Press. · Zbl 0129.00802
[263] Sakuraba, C. S., & Yagiura, M. (2009). Efficient local search algorithms for the linear ordering problem (submitted for publication). · Zbl 1220.90154
[264] Schiavinotto, T., & Stützle, T. (2003). Search space analysis of the linear ordering problem. In G. R. Raidl et al. (Eds.), Lecture notes in computer science : Vol. 2611. Applications of evolutionary computing (pp. 322–333). Berlin: Springer. · Zbl 1033.90512
[265] Schiavinotto, T., & Stützle, T. (2004). The linear ordering problem: instances, search space analysis and algorithms. Journal of Mathematical Modelling and Algorithms, 3(4), 367–402. · Zbl 1079.90117 · doi:10.1023/B:JMMA.0000049426.06305.d8
[266] Schrijver, A. (2003). Combinatorial optimization. Polyhedra and efficiency. Berlin: Springer. · Zbl 1041.90001
[267] Schwartz, T. (1990). Cyclic tournaments and cooperative majority voting: a solution. Social Choice and Welfare, 7, 19–29. · Zbl 0698.90008 · doi:10.1007/BF01832917
[268] Seymour, P. (1995). Packing directed circuits fractionally. Combinatorica, 15(2), 281–288. · Zbl 0826.05031 · doi:10.1007/BF01200760
[269] Slater, P. (1961). Inconsistencies in a schedule of paired comparisons. Biometrika, 48, 303–312.
[270] Smith, W. D. (2007). http://rangevoting.org/PuzzDG.html .
[271] Smith, A. F. M., & Payne, C. D. (1974). An algorithm for determining Slater’s i and all nearest adjoining orders. British Journal of Mathematical and Statistical Psychology, 27, 49–52.
[272] Spencer, J. (1971). Optimal ranking of tournaments. Networks, 1, 135–138. · Zbl 0236.05110 · doi:10.1002/net.3230010204
[273] Spencer, J. (1978). Nonconstructive methods in discrete mathematics. In G. C. Rota (Ed.), Studies in combinatorics (pp. 142–178). Washington: Mathematical Association of America. · Zbl 0407.05001
[274] Spencer, J. (1987). CBMS-NSF regional conference series in applied mathematics : Vol. 52. Ten lectures on the probabilistic method. Philadelphia: SIAM.
[275] Stearns, R. (1959). The voting problem. American Mathematical Monthly, 66, 761–763. · Zbl 0090.25101 · doi:10.2307/2310461
[276] Szele, T. (1943). Kombinatorikai vizsgálatok az irányított teljes gráffal kapesolatban. Matematikai és Fizikai Lapok, 50, 223–256. German translation: Untersuchungen über gerichtete vollständige Graphen. Publicationes Mathematical Debrecen, 13, 145–168 (1966).
[277] Thomassen, C. (1975). Transversals of circuits in the lexicographic product of directed graphs. Mathématiques et Sciences humaines, 51, 43–45. · Zbl 0315.05109
[278] Thomassen, C. (1987). Counterexamples to Adám’s conjecture on arc reversals in directed graphs. Journal of Combinatorial Theory Series B, 42, 128–130. · Zbl 0609.05041 · doi:10.1016/0095-8956(87)90068-2
[279] Tucker, A. W. (1960). On directed graphs and integer programs. In 1960 Symposium on combinatorial problems. Princeton: Princeton University.
[280] Tüshaus, U. (1983). Mathematical systems in economics : Vol. 82. Aggregation binärer Relationen in der qualitativen Datenanalyse. Königstein: Verlagsgruppe Athenäum/Hain/Hanstein.
[281] van Zuylen, A. (2005). Deterministic approximation algorithms for ranking and clusterings (Cornell ORIE Tech. Report No. 1431).
[282] van Zuylen, A., & Williamson, D. P. (2008). Deterministic algorithms for rank aggregation and other ranking and clustering problems. In C. Kaklamanis & M. Skutella (Eds.), LNCS : Vol. 4927. Approximation and online algorithms (pp. 260–273). Berlin: Springer. · Zbl 1130.68342
[283] Vazirani, V. V. (2003). Approximation algorithms. Berlin: Springer.
[284] Wakabayashi, Y. (1986). Aggregation of binary relations: algorithmic and polyhedral investigations. Ph.D. thesis, Augsburg university. · Zbl 0606.68036
[285] Wakabayashi, Y. (1998). The complexity of computing medians of relations. Resenhas, 3(3), 323–349. · Zbl 1098.68618
[286] Wei, T. (1952). The algebraic foundations of ranking theory. Ph.D. thesis, Cambridge University.
[287] Wessels, H. (1981). Triangulation und Blocktriangulation von Input-Output Tabellen. Deutsches Institut für Wirtschaftsforschung: Beiträge zur Strukturforshung, Heft 63, Berlin.
[288] Woeginger, G. J. (2003). Banks winners in tournaments are difficult to recognize. Social Choice and Welfare, 20(3), 523–528. · Zbl 1073.05538 · doi:10.1007/s003550200197
[289] Woirgard, F. (1997). Recherche et dénombrement des ordres médians des tournois. Ph.D. thesis, ENST, Paris.
[290] Wolsey, L. (1998). Integer programming. New York: Wiley. · Zbl 0930.90072
[291] Young, H. P. (1978). On permutations and permutation polytopes. Mathematical Programming Study, 8, 128–140. · Zbl 0424.05001
[292] Young, H. P. (1988). Condorcet theory of voting. American Political Science Review, 82, 1231–1244. · doi:10.2307/1961757
[293] Younger, D. H. (1963). Minimum feedback arc sets for a directed graph. IEEE Transactions on Circuit Theory, 10(2), 238–245. · doi:10.1109/TCT.1963.1082116
[294] Zermelo, E. (1929). Die Berechnung der Turnier-Ergebnisse als ein maximal Problem der Warscheinlichkeistsrechnung. Mathematische 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.