Academic
Publications
On the Advantage over Random for Maximum Acyclic Subgraph

On the Advantage over Random for Maximum Acyclic Subgraph,10.1109/FOCS.2007.47,Electronic Colloquium on Computational Complexity,Moses Charikar,Konsta

On the Advantage over Random for Maximum Acyclic Subgraph   (Citations: 7)
BibTex | RIS | RefWorks Download
In this paper we present a new approximation algo- rithm 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 with1/2 + (�/logn) fraction of all edges.
Journal: Electronic Colloquium on Computational Complexity - ECCC , vol. 14, no. 104, pp. 625-633, 2007
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...They have found application to problems ranging from Constraint Satisfaction Problems [7, 28, 22, 19, 9, 12] to Vertex Coloring [21, 11, 2, 13], Vertex Ordering [8, 14] to Graph decomposition [15, 3], and Discrete optimization [1, 10, 25, 31]...

    Prasad Raghavendraet al. How to Round Any CSP

    • ...For the MAS problem, the authors of [6] showed how to use a construction of a directed acyclic graph with low cut-norm due to Charikar, Makarychev, and Makarychev [2] to obtain the required gap instance...

    Moses Charikaret al. Every Permutation CSP of arity 3 is Approximation Resistant

    • ...The starting point of our reduction is a directed acyclic subgraph (DAG) in which every cut is nearly-balanced in the sense that the number of forward and backward edges crossing the cut are nearly equal; such DAGs were constructed in [2]...
    • ...Recently, Charikar, Makarychev, and Makarychev [2] gave a factor (1=2 + (1 = logn))-approximation algorithm for MAX ACYCLIC SUBGRAPH, where n is the number of vertices...
    • ...This algorithm and, in particular, an instance showing tightness of its analysis from [2], play a crucial role in our work...
    • ...For any fixed constant t, Charikar, Makarychev and Makarychev [2] construct directed acyclic graphs (i.e., with value of the best ordering equal to 1), while the value of any t-ordering of G is close to 1 2 . For...
    • ...theorem from [2] relating the cut norm of a directed graph G to Val(G)...
    • ...Proof. Charikar et al (Section 4, [2]) construct a directed graph, G = (V;E), on n vertices whose cut norm is bounded by O (1= logn)...

    Venkatesan Guruswamiet al. Beating the Random Ordering is Hard: Inapproximability of Maximum Acyc...

    • ...For the MAS problem, the authors of [6] showed how to use a construction of a directed acyclic graph with low cut-norm due to Charikar, Makarychev, and Makarychev [2] to obtain the required gap instance...

    Moses Charikaret al. Every Permutation CSP of arity 3 is Approximation Resistant

Sort by: