Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
From MaRDI portal
Publication:3088101
DOI10.1007/978-3-642-22935-0_24zbMath1343.68313arXiv0911.2214MaRDI QIDQ3088101
Marek Karpinski, Warren Schudy
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
Related Items
Kernel and fast algorithm for dense triplet inconsistency, On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments, Partial Kernelization for Rank Aggregation: Theory and Experiments
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
