Improved approximation algorithms for maximum graph partitioning problems

DOI10.1007/s10878-005-2269-7zbMath1093.90069OpenAlexW1514508085MaRDI QIDQ813332

Gerold Jäger, Anand Srivastav

Publication date: 8 February 2006

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-005-2269-7

zbMATH Keywords

semidefinite programmingapproximation factormaximum graph partitioning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22)

Related Items (13)

Numerical Study of Semidefinite Bounds for the k-cluster Problem ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Super-polynomial approximation branching algorithms ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Approximation algorithms for MAX RES CUT with limited unbalanced constraints ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ An approximation algorithm for the partial vertex cover problem in hypergraphs ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ A randomised approximation algorithm for the hitting set problem ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ Randomized approximation for the set multicover problem in hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
• An improved rounding method and semidefinite programming relaxation for graph partition
• A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• Greedily Finding a Dense Subgraph
• The dense \(k\)-subgraph problem
• A .699-approximation algorithm for Max-Bisection.

This page was built for publication: Improved approximation algorithms for maximum graph partitioning problems