On the Advantage over Random for Maximum Acyclic Subgraph
Authors:
- Moses CharikarMCMoses Charikar
- Konstantin MakarychevKMKonstantin Makarychev
- Yury MakarychevYMYury Makarychev
- 1 October 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 14 (02725428) , 625-633
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 + delta fraction of all edges, our algorithm finds an acyclic subgraph with 1/2 + Omega(delta/ log n) fraction of all edges.Keywords
This publication has 15 references indexed in Scilit:
- On the advantage over a random assignmentRandom Structures & Algorithms, 2004
- Is constraint satisfaction over two variables always easy?Random Structures & Algorithms, 2004
- Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering ProblemLecture Notes in Computer Science, 2004
- The Maximum Acyclic Subgraph Problem and Degree-3 GraphsLecture Notes in Computer Science, 2001
- Fences Are Futile: On Relaxations for the Linear Ordering Problem2001
- A New Way of Using Semidefinite Programming with Applications to Linear Equations mod pJournal of Algorithms, 2001
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Packing directed circuits fractionallyCombinatorica, 1995
- Approximations for the maximum acyclic subgraph problemInformation Processing Letters, 1994
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991