2009/11/11 by Marek Karpiński, Karpinski, Marek, Warren Schudy +1
Computer Science · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.1 #G.2.2 #G.3 #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.0911.2214
openalex publication_date 2009/11/11 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
We design the first polynomial time approximation schemes (PTASs) for the\nMinimum Betweenness problem in tournaments and some related higher arity\nranking problems. This settles the approximation status of the Betweenness\nproblem in tournaments along with other ranking problems which were open for\nsome time now. The results depend on a new technique of dealing with fragile\nranking constraints and could be of independent interest.\n