On the complexity of Slater's problems

被引：12

作者：

Hudry, Olivier ^{[1
]}

机构：

[1] Ecole Natl Super Telecommun Bretagne, F-75634 Paris 13, France

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2010年 / 203卷 / 01期

关键词：

Complexity; Tournament solutions; Slater solution; Majority tournament; BANKS WINNERS; TOURNAMENTS; RECOGNIZE; DIFFICULT;

D O I：

10.1016/j.ejor.2009.07.034

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

Given a tournament T. Slater's problem consists in determining a linear order (i.e. a complete directed graph without directed cycles) at minimum distance from T, the distance between T and a linear order O being the number of directed edges with different orientations in T and in O. This paper studies the complexity of this problem and of several variants of it: computing a Slater order, computing a Slater winner, checking that a given vertex is a Slater winner and so on. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：216 / 221

页数：6

共 50 条

[31] Complexity analysis for certain convex programming problems
Darracq, MC
[J]. JOURNAL OF COMPLEXITY, 1999, 15 (02) : 282 - 293
[32] Complexity of product positioning and ball intersection problems
Crama, Y
Hansen, P
Jaumard, B
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1995, 20 (04) : 885 - 894
[33] THE PARALLEL COMPLEXITY OF COARSEST SET PARTITION PROBLEMS
SANG, C
HUYNH, DT
[J]. INFORMATION PROCESSING LETTERS, 1992, 42 (02) : 89 - 94
[34] On the complexity of some quorum colorings problems of graphs
Sahbi, Rafik
[J]. AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (03) : 784 - 787
[35] PROBLEMS OF COMPREHENDING COMPLEXITY IN DOMESTIC AND FOREIGN PHILOSOPHY
Opolev, Pavel V.
[J]. VESTNIK TOMSKOGO GOSUDARSTVENNOGO UNIVERSITETA-FILOSOFIYA-SOTSIOLOGIYA-POLITOLOGIYA-TOMSK STATE UNIVERSITY JOURNAL OF PHILOSOPHY SOCIOLOGY AND POLITICAL SCIENCE, 2023, 71 : 128 - 137
[36] On the complexity of a class of combinatorial optimization problems with uncertainty
Averbakh, I
[J]. MATHEMATICAL PROGRAMMING, 2001, 90 (02) : 263 - 272
[37] Complexity of general continuous minimization problems: a survey
Gaviano, M
Lera, D
[J]. OPTIMIZATION METHODS & SOFTWARE, 2005, 20 (4-5) : 525 - 544
[38] Labeled Traveling Salesman Problems: Complexity and approximation
Couetoux, Basile
Gourves, Laurent
Monnot, Jerome
Telelis, Orestis A.
[J]. DISCRETE OPTIMIZATION, 2010, 7 (1-2) : 74 - 85
[39] On the complexity of solving feasibility problems with regularized models
Birgin, E. G.
Bueno, L. F.
Martinez, J. M.
[J]. OPTIMIZATION METHODS & SOFTWARE, 2022, 37 (02) : 405 - 424
[40] THE COMPLEXITY OF COMBINATIONS OF QUALITATIVE CONSTRAINT SATISFACTION PROBLEMS
Bodirsky, Manuel
Greiner, Johannes
[J]. LOGICAL METHODS IN COMPUTER SCIENCE, 2020, 16 (01)

← 1 2 3 4 5 →