O( n) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems

DOI10.1145/1060590.1060675MaRDI QIDQ3581406zbMATH OpenOpenAlexFDO

Authors Amit Agarwal, Konstantin Makarychev, Yury Makarychev, Moses Charikar

Publication date 16 August 2010

Published in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1060590.1060675

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 2079369
• Approximation and Online Algorithms
• An O( n)-approximation algorithm for directed sparsest cut
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• On the hardness of approximating Multicut and Sparsest-Cut

Cited in

(56)

• An O( n)-approximation algorithm for directed sparsest cut
• Approximation and hardness results for the max \(k\)-uncut problem
• Optimizing adiabatic quantum program compilation using a graph-theoretic framework
• Towards a characterization of constant-factor approximable finite-valued CSPs
• Affine reductions for LPs and SDPs
• Colocating tasks in data centers using a side-effects performance model
• Stabilizing network bargaining games by blocking players
• On the complexity of minimum \(q\)-domination partization problems
• Faster graph bipartization
• Complexity and approximation of the minimum recombinant haplotype configuration problem
• On approximability of optimization problems related to red/blue-split graphs
• Approximation of the quadratic set covering problem
• Inoculation strategies for victims of viruses and the sum-of-squares partition problem
• New algorithms for a simple measure of network partitioning
• On polynomial kernels for structural parameterizations of odd cycle transversal
• Approximation and hardness results for the max \(k\)-uncut problem
• Complexity of approximating CSP with balance/hard constraints
• Stabilizing network bargaining games by blocking players
• Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
• Approximation and kernelization for chordal vertex deletion
• Approximation algorithms for digraph width parameters
• Approximation Algorithms for CSPs
• Approximating unique games using low diameter graph decomposition
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Hitting weighted even cycles in planar graphs
• Correlation clustering generalized
• An Updated Experimental Evaluation of Graph Bipartization Methods
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• The maximum congested cut problem and its robust counterpart: Exact and approximation algorithms for the single and the multicommodity case
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
• Approximating max k-uncut via LP-rounding plus greed, with applications to densest k-subgraph
• A modeling and computational study of the frustration index in signed networks
• New algorithms for a simple measure of network partitioning
• Separator-based data reduction for signed graph balancing
• Timeline cover in temporal graphs: exact and approximation algorithms
• The complexity of König subgraph problems and above-guarantee vertex cover
• Approximation algorithm for minimum \(q\)-dominator partization problem
• Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
• Storylines with a protagonist
• Bipartizing (pseudo-)disk graphs: approximation with a ratio better than 3
• Exact and approximation algorithms for covering timeline in temporal graphs
• On the complexity of winner determination and strategic control in conditional approval voting
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• Efficient parameterized approximation
• All-subsets important separators with applications to sample sets, balanced separators and vertex sparsifiers in directed graphs
• Min-CSPs on complete instances. II: Polylogarithmic approximation for Min-NAE-3-SAT
• Density Frankl-Rödl on the sphere
• O( n)-approximation algorithms for bipartiteness ratio
• \(\ell ^2_2\) spreading metrics for vertex ordering problems
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• The multi-multiway cut problem
• Finding small stabilizers for unstable graphs
• Approximation algorithms for the Bipartite Multicut problem

This page was built for publication: \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581406)