|
|||||
|
|
An LP-rounding -approximation for restricted maximum acyclic subgraph |
|
| Authors: | Fabrizio Grandoni Tomasz Kociumaka Michał Włodarczyk |
| Affiliation: | 1. IDSIA, University of Lugano, Switzerland;2. Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland |
| Abstract: | 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 forward-directed edges. MAS admits a 2-approximation, and this approximation is optimal under the Unique Game Conjecture. |
| Keywords: | Approximation algorithms Directed graphs Vertex pricing Linear programming Derandomization |
| 本文献已被 ScienceDirect 等数据库收录！ | |