On the advantage over random for maximum acyclic subgraph

Moses Charikar; Konstantin Makarychev; Yury Makarychev

doi:10.1109/FOCS.2007.4389531

FOCS 2007

Conference paper

01 Dec 2007

On the advantage over random for maximum acyclic subgraph

View publication

Abstract

In this paper we present a new approximation algorithm for the MAX ACYCLIC SUBGRAPH problem. Given an instance where the maximum acyclic subgraph contains 1/2 + δ fraction of all edges, our algorithm finds an acyclic subgraph with 1/2 + Ω(δ/ log n) fraction of all edges. © 2007 IEEE.

Conference paper