Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems

DOI10.1007/978-3-642-22935-0_24zbMath1343.68313arXiv0911.2214OpenAlexW1595088992MaRDI QIDQ3088101

Warren Schudy, Marek Karpinski

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0911.2214

Mathematics Subject Classification ID

Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (4)

Kernel and fast algorithm for dense triplet inconsistency ⋮ Unnamed Item ⋮ Partial Kernelization for Rank Aggregation: Theory and Experiments ⋮ On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quick approximation to matrices and applications
• Betweenness parameterized above tight lower bound
• Hardness of fully dense problems
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• Random sampling and approximation of MAX-CSP problems
• Fast FAST
• Total Ordering Problem
• A Geometric Approach to Betweenness
• Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
• Aggregating inconsistent information

This page was built for publication: Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems