A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams

DOI10.1016/j.dam.2023.04.016MaRDI QIDQ6162034

Matthew Drescher, Tony Huynh, Samuel Fiorini, Manuel Aprile

Publication date: 15 June 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmtournamentsfeedback vertex setintegrality gapSherali-Adams hierarchy

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Mathematical programming (90Cxx) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sophisticated voting outcomes and agenda control
• On a conjecture of Tuza about packing and covering of triangles
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A 7/3-Approximation for Feedback Vertex Sets in Tournaments
• A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
• Quasi-PTAS for scheduling with precedences using LP hierarchies
• 2-Approximating Feedback Vertex Set in Tournaments
• 2-Approximating Feedback Vertex Set in Tournaments
• A tight approximation algorithm for the cluster vertex deletion problem

This page was built for publication: A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams