On the advantage over random for maximum acyclic subgraph

Moses Charikar*, Konstantin Makarychev, Yury Makarychev

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Pages625-633
Number of pages9
DOIs
StatePublished - Dec 1 2007
Event48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States
Duration: Oct 20 2007Oct 23 2007

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other48th Annual Symposium on Foundations of Computer Science, FOCS 2007
CountryUnited States
CityProvidence, RI
Period10/20/0710/23/07

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'On the advantage over random for maximum acyclic subgraph'. Together they form a unique fingerprint.

Cite this