An LP-Rounding $2\sqrt{2}$ Approximation for Restricted Maximum Acyclic Subgraph

Fabrizio Grandoni, Tomasz Kociumaka, Michał Włodarczyk

In the classical Maximum Acyclic Subgraph problem (MAS), given a directed-edge weighted graph, we are required to find an ordering of the nodes that maximizes the total weight of f…